By Contest Road to Fortaleza V Brazil
Petr is playing a game called "Jumping Stones".
In this game, there are N slots in a line numbered from 1 to N. On each slot there is a stone with a number written on its top. The written numbers go from 1 to N and are all different.
Petr starts at slot 1 and takes K steps. At each step, he looks the number written on the current stone and jumps to the slot correspondent to that number.
Given integers N and K, determine among all possible configurations the probability that he will return to slot 1 after K steps. Assume that different configurations has the same probability.
You will be given T, number of test cases, and then T lines follow with N and K from the statement (1 <= N,K <= 10^5).
For each test case output a single line with the answer. Your answer will be considered correct if the absolute erro is less than 0.00001
Ps.: Following the example input For the second case we have the following possibilites:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
In the first and second configurations we finish at the slot 1 after 1 step.
|Sample Input||Sample Output|