Description

Xiao Q is a student who loves studying, but he has recently been obsessed with various games, and Dungeons and Dragons is one of them.

In this game, many situations require rolling dice to generate random numbers, which then determine the character’s fate. Therefore, dice are iconic props in this game.

There are many kinds of dice, such as the $4$-sided die, $6$-sided die, $8$-sided die, $12$-sided die, and $20$-sided die, among which the $20$-sided die is used very often. Of course, with modern technology, a random number generator can replace a real die, so here we assume that a die is a random number generator.

In battles, dice are mainly used to determine whether an attack hits and, if it hits, the damage dealt. For example, suppose we already know the attack will hit; then $YdX$ (i.e., roll $Y$ $X$-sided dice and sum all numbers shown) is the base damage dealt to the enemy. If the enemy has no defense, this base damage is the actual damage.

It is well known that each face of a die has the same probability. That is, for an $X$-sided die, each number among $0, 1, 2, \dots, X-1$ appears with probability $\dfrac{1}{X}$.

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

$W$	$0$	$1$	$2$	$\cdots$	$X-1$
$P$	$\dfrac {1}{X}$			$\cdots$	$\dfrac {1}{X}$

In addition, it has the following properties:

• The first raw moment (expectation) of $W$ is

$$v_1(W)=E(W)=\sum_{i=0}^{X-1}i\cdot P(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))^2\cdot P(W=i)=\frac {X^2-1}{12}.$$

Back to the point: Now Xiao Q faces an enemy with health $A$, has no defense, and he can make one guaranteed-hit $YdX$ attack. Obviously, only damage not less than the enemy’s health can defeat the enemy. On the other hand, as a perfectionist, Xiao Q does not want “overkill,” i.e., dealing damage greater than $B$. Therefore, Xiao Q considers it his victory only if he both defeats the enemy and does not have “overkill.”

Because Xiao Q is very cautious, he will run $10$ mock battles. Each time, he gives the enemy’s health $A$ and the overkill threshold $B$. He wants to know the probability of achieving his own victory under these conditions. Can you help him?

Input Format

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

For each test case:

• The first line contains two integers $X, Y$, the number of faces of the die and the number of dice, respectively.
• Then follow $10$ lines, each containing two integers $A, B$, representing the enemy’s health $A$ and the overkill threshold $B$.

Output Format

For each test case, output $10$ lines. For each query, output a real number. The absolute error must not exceed $0.013\, 579$.

That is, let the output be $a$ and the correct answer be $b$. If $|a-b|\leq 0.013\,579$, the output is considered correct.

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

0.000002
0.000038
0.000364
0.002213
0.009605
0.031784
0.083534
0.179642
0.323803
0.500000

Hint

For $100\%$ of the testdata, $T \leq 10$, $2 \leq X \leq 20$, $1 \leq Y \leq 200000$, $0 \leq A \leq B \leq (X-1)Y$.

It is guaranteed that there are at most $2$ test cases with $Y > 800$.

Test point ID	$X$	$Y$	Note
$1$	$\le 20$	$\le 40$	$X^Y\le 10^7$
$2\sim 4$		$\le 1\, 600$	-
$5\sim 10$		$\le 8\, 000$
$11,12$	$=2$	$\le 200\, 000$
$13\sim 20$	$\le 20$

Translated by ChatGPT 5