Scrooge McDuck obtained a plan of the ancient Mayaduck labyrinth full of gold and other treasures. He knows that there are exactly n rooms in the labyrinth and he would like to visit all of them to take all fortune. Every room has exactly one exit to some other room. Every room has no more than one entry from some other room. The main problem is that there are no ways between labyrinth and outer space, and between some pairs of rooms. Scrooge decided to use Duck Teleportation Company Unit to resolve this case. He can teleport to every room inside labyrinth or outside. But there is another problem: every jump costs a huge amount of money and McDuck needs to minimize the number of teleportations.
On the Scrooge's plan rooms are numerated from 1 to N and in every room there is a written room number where one could go to. Unfortunately some numbers are damaged by age and are now unreadable.
You should find the expected amount of money Scrooge needs to investigate all rooms and come back out of the labyrinth, provided that his strategy is optimal and all possible configurations of labyrinth are equiprobable. He begins his journey from outside of the labyrinth. The first jump Scrooge makes for free.
On the first line of input an integer number T (0 < T ≤ 100) is given — the total number of testcases. Every testcase is described by two lines. On the first line there are two integers 1 < N ≤ 4000 — the number of rooms and 0 ≤ c ≤ 1000 — the cost of one jump. On the second line there are N numbers, 0 ≤ ai ≤ N — room number one can go directly from ith room. If any room number is unreadable then ai = 0. All testcases are separated by an empty line. The sum of N in all cases doesn't exceed 4000. It is guaranteed that all input cases are correct, i.e. there exists at least one plan corresponding to the input data.
For every input case you should output one floating point number on a separate line — the answer for the problem with absolute or relative precision of 10 - 6.
## Input
On the first line of input an integer number T (0 < T ≤ 100) is given — the total number of testcases. Every testcase is described by two lines. On the first line there are two integers 1 < N ≤ 4000 — the number of rooms and 0 ≤ c ≤ 1000 — the cost of one jump. On the second line there are N numbers, 0 ≤ ai ≤ N — room number one can go directly from ith room. If any room number is unreadable then ai = 0. All testcases are separated by an empty line. The sum of N in all cases doesn't exceed 4000. It is guaranteed that all input cases are correct, i.e. there exists at least one plan corresponding to the input data.
## Output
For every input case you should output one floating point number on a separate line — the answer for the problem with absolute or relative precision of 10 - 6.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ N \in \mathbb{Z} $ be the number of rooms, with $ 1 < N \leq 4000 $.
- Let $ c \in \mathbb{R} $ be the cost per teleportation.
- Let $ A = (a_1, a_2, \dots, a_N) $, where $ a_i \in \{0\} \cup \{1, 2, \dots, N\} $, denote the directed edges:
- If $ a_i = 0 $, the exit from room $ i $ is **unknown** (unspecified).
- If $ a_i > 0 $, the exit from room $ i $ leads deterministically to room $ a_i $.
The labyrinth is a partial functional graph: each room has **at most one outgoing edge** and **at most one incoming edge**.
Let $ \mathcal{F} $ be the set of all valid complete assignments $ f: \{1,\dots,N\} \to \{1,\dots,N\} $ such that:
- $ f(i) = a_i $ for all $ i $ with $ a_i > 0 $,
- $ f(i) \in \{1,\dots,N\} $ for all $ i $ with $ a_i = 0 $,
- The resulting directed graph has in-degree $ \leq 1 $ and out-degree $ = 1 $ for every node.
Each assignment $ f \in \mathcal{F} $ is equally probable.
**Constraints**
1. $ 0 < T \leq 100 $
2. $ 1 < N \leq 4000 $, $ 0 \leq c \leq 1000 $
3. $ \sum_{\text{test cases}} N \leq 4000 $
4. $ |\mathcal{F}| \geq 1 $ (at least one valid configuration exists)
**Objective**
Compute the **expected number of teleportations** required for Scrooge to visit all $ N $ rooms and exit the labyrinth, given:
- He starts **outside** the labyrinth.
- The **first teleportation is free**.
- Each subsequent teleportation costs $ c $, but we count **number of jumps**, not cost.
- He follows the deterministic path defined by $ f $: from room $ i $, he moves to $ f(i) $.
- He can teleport to **any room** (or outside) at will, and his strategy is **optimal** (minimizes expected jumps).
Let $ J(f) $ be the **minimum number of teleportations** needed to visit all rooms and exit, under mapping $ f $.
We are to compute:
$$
\mathbb{E}[J] = \frac{1}{|\mathcal{F}|} \sum_{f \in \mathcal{F}} J(f)
$$
Note: Since the first jump is free, $ J(f) $ counts **only the teleportations after the initial free one**.
The journey ends when all rooms are visited and Scrooge exits (i.e., teleports out after last room).
**Key Insight**:
The graph under $ f $ is a disjoint union of **cycles** and **chains ending in cycles** (functional graph).
To visit all nodes optimally:
- Scrooge must teleport into each **connected component** (weakly connected component of the functional graph).
- Once inside a component, he can traverse the entire component via following the deterministic edges.
- He must teleport out after the last room.
Thus, for a given $ f $:
Let $ k(f) $ = number of **weakly connected components** (i.e., number of cycles + chains feeding into them).
Then:
- 1 free teleportation to enter first component.
- $ k(f) - 1 $ teleportations to enter remaining components.
- 1 final teleportation to exit.
So:
$$
J(f) = (k(f) - 1) + 1 = k(f)
$$
Therefore:
$$
\boxed{\mathbb{E}[J] = \mathbb{E}[k]}
$$
**Final Objective**:
Compute the **expected number of weakly connected components** in a random valid functional graph on $ N $ nodes, where some edges are fixed and others are uniformly chosen among all valid completions respecting in-degree $ \leq 1 $.