G. Iguana Walking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the mystical land of Iguanaria, there exists a unique community of iguanas. Each iguana is designated by a distinct integer from 1 to N. Among these iguanas, Iguana 1 is considered the leader. These iguanas have a mystical connection that draws them towards Iguana 1. They embark on a journey to find their leader, guided solely by their intuition.

You are given an array $$$p$$$, where $$$p_i$$$ means that on each time step, the iguana at position $$$i$$$ will move to position $$$p_i$$$. Note that Iguana 1 will send an assistant to move for it, and will remain at position $$$1$$$ throughout the duration of the movements.

However, the journey is not without challenges. The Iguanaria is a dense rainforest filled with obstacles, and some iguanas may never reach Iguana 1 due to their wandering paths or the perils they encounter. Your task is to calculate the expected time it takes for the iguanas that can reach their leader, Iguana 1, to find him, starting from $$$t = 0$$$.

Input

The first line contains $$$T(1\leq T\leq 2\cdot 10^5)$$$, the number of test cases.

The first line of each test case contains $$$N (1\leq N \leq 2\cdot 10^5)$$$, the total number of iguanas.

The second line of each test case contains $$$N$$$ integers: $$$p_1, p_2, \ldots, p_n (1\leq p_i\leq N)$$$ which is the array $$$p$$$.

Additionally, the sum of $$$N$$$ over all test cases does not exceed $$$2\cdot 10^5$$$

Output

For each test case print one number, the expected time for the iguanas that can reach Iguana 1 to find him. Numbers within $$$10^{-6}$$$ of our answer will be considered correct.

Example
Input
3
5
5 2 3 1 4
3
1 2 3
10
2 3 4 5 6 7 8 9 10 1
Output
1.000000000000000
0.000000000000000
4.500000000000000
Note

Your calculation should include the expected time for Iguana 1 to reach Iguana 1.