bee 1703 - Jumping Stones

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.

Input

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).

Output

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
2 1 1 3 1	1.000000 0.333333

Sample Input

Sample Output

1 1

3 1

1.000000

0.333333