402171: GYM100685 H Hunt for Treasure!

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 ≤ a_i ≤ N  — room number one can go directly from i^th room. If any room number is unreadable then a_i = 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.

3
2 1
0 0

3 2
2 3 1

4 1
0 0 0 0

1.000000
2.000000
1.333333