Migrated from Lutece 747 Birthday Party

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$N$ persons have been invited to a somewhat special birthday party. Each person brings one present, but the recipent of each present is determined randomly. A person never receives his own present, but all other persons are equally likely recipients. What is the probability that one can find $k$ persons at the party such that person $1$ gives his present to person $2$, person $2$ gives his present to person $3$ and so on to person $k$ which gives his present to person $1$?

Input

The first line of the input consists of a single integer $T$, the number of test cases. Each test case consists of two integers $N$ and $k$.

Output

For each test case, output the probability with an accuracy of at least $10^{-6}$

Samples

4
2 2
3 2
3 3
10 3

1.000000000
0.750000000
0.250000000
0.313469843

Note

$0 < T \leq 30$

$2 \leq N \leq 10000000$

$2 \leq k \leq N$

Resources

IDI Open Programming Contest April 21st, 2012 - NTNU