Student Q is a person who loves to learn, but he has recently become addicted to various games, and Dungeons & Dragons is one of them.

In this game, it is often necessary to roll dice to generate random numbers, which then determine the future fate of a character. Therefore, dice are iconic items in this game.

There are many types of dice, such as 4-sided, 6-sided, 8-sided, 12-sided, and 20-sided dice, with 20-sided dice being used very frequently. Of course, with modern technology, a random number generator can replace physical dice, so here we consider a die to be a random number generator.

In combat, dice are mainly used to determine whether a character's attack hits, and the damage dealt upon a hit. For example, assuming it is already determined that the attack hits the enemy, then $Y dX$ (which is the sum of the numbers shown on $Y$ $X$-sided dice) is the base damage to the enemy. If the enemy has no defense, this base damage is the true damage.

As everyone knows, the probability of a die showing each number should be equal. That is to say, for an $X$-sided die, the probability of showing any number in $0, 1, 2, \dots, X-1$ is $\frac{1}{X}$.

More formally, the number $W$ shown by this die satisfies a discrete uniform distribution, with the distribution table:

In addition, there are some properties: The first raw moment (expectation) of $W$ is $\nu_1(W) = E(W) = \sum_{i=0}^{X-1} iP(W = i) = \frac{X-1}{2}$ The second central moment (variance) of $W$ is $\mu_2(W) = E((W - E(W))^2) = \sum_{i=0}^{X-1} (i - E(W))^2P(W = i) = \frac{X^2-1}{12}$

Getting down to business, Student Q is now facing an enemy with $A$ health and no defense, and can launch a guaranteed-hit $Y dX$ attack. Obviously, only if the damage dealt is no less than the enemy's health can the enemy be defeated. On the other hand, as a perfectionist, Student Q does not want "overkill" to occur, which means the damage dealt should not exceed $B$. Therefore, Student Q only considers it a victory if the enemy is defeated without overkill occurring.

Because Student Q is very cautious, he will conduct 10 simulated battles. For each, he provides the enemy's health $A$ and the overkill threshold $B$. He wants to know the probability of achieving his victory. Can you help him?

Input

The first line is a positive integer $T$, representing the number of test cases.

For each test case: The first line contains two integers $X, Y$, representing the number of sides of the dice and the number of dice, respectively. The next 10 lines each contain two integers $A, B$, representing the enemy's health $A$ and the overkill threshold $B$.

Output

For each test case, output 10 lines. For each query, output a real number. The absolute error is required to be no more than $0.013579$. That is, if the output is $a$ and the answer is $b$, the output is considered correct if $|a - b| \le 0.013579$.

Examples

Input 1

1
2 19
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9

Output 1

0.000002
0.000038
0.000364
0.002213
0.009605
0.031784
0.083534
0.179642
0.323803
0.500000

Note

For 100% of the data, $T \le 10$, $2 \le X \le 20$, $1 \le Y \le 200000$, $0 \le A \le B \le (X - 1)Y$. It is guaranteed that there are no more than 2 test cases where $Y > 800$.