Birthday Party

$N$ people are invited to a birthday party. Each of them brings one present, and the person who receives that present is picked at random. Nobody gives a present to themselves, and each of the other $N-1$ people is equally likely to be picked. The choices are independent, so one guest can receive several presents while another receives none.

Call a gift cycle a set of $k$ distinct guests $p_1, p_2, \dots, p_k$ such that $p_1$ gives their present to $p_2$, $p_2$ gives theirs to $p_3$, and so on until $p_k$ gives theirs back to $p_1$. Find the probability that at least one gift cycle of length $k$ appears.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $N$ and $k$ separated by a space.

• $0 < T \le 30$
• $2 \le N \le 10^7$
• $2 \le k \le N$

For each test case, print the probability on its own line, rounded to exactly six digits after the decimal point. Print 1.000000 when the probability is $1$, and 0.313470 when it is $0.313469843\ldots$