描述

小Q同学是一个热爱学习的人，但是他最近沉迷于各种游戏，龙与地下城就是其中之一。

在这个游戏中，很多场合需要通过掷骰子来产生随机数，并由此决定角色未来的命运，因此骰子堪称该游戏的标志性道具。

骰子也分为许多种类，比如\(4\)面骰、\(6\)面骰、\(8\)面骰、\(12\)面骰、\(20\)面骰，其中\(20\)面骰用到的机会非常多。
当然，现在科技发达，可以用一个随机数生成器来取代真实的骰子，所以这里认为骰子就是一个随机数生成器。

在战斗中，骰子主要用来决定角色的攻击是否命中，以及命中后造成的伤害值。
举个例子，假设现在已经确定能够命中敌人，那么\(YdX\)（也就是掷出\(Y\)个\(X\)面骰子之后所有骰子显示的数字之和）就是对敌人的基础伤害。
在敌人没有防御的情况下，这个基础伤害就是真实伤害。

众所周知，骰子显示每个数的概率应该是相等的，也就是说，对于一个\(X\)面骰子，显示\(0,1,2,...,X-1\)中每一个数字的概率都是\(\frac{1}{X}\)。

除此之外还有一些性质：

\(W\)的一阶原点矩(期望)为\(\nu_1(W)=E(W)=\sum\limits_{i=0}^{X-1}iP(W=i)=(X-1)/{2}\)；

\(W\)的二阶中心矩(方差)为\(\mu_2(W)=E((W-E(W))^2)=\sum\limits_{i=0}^{X-1}(i-E(W))^2P(W=i)=(X^2-1)/{12}\)。

言归正传，现在小Q同学面对着一个生命值为\(A\)的没有防御的敌人，能够发动一次必中的\(YdX\)攻击，显然只有造成的伤害不少于敌人的生命值才能打倒敌人。
但是另一方面，小Q同学作为强迫症患者，不希望出现overkill，也就是造成的伤害大于\(B\)的情况，因此只有在打倒敌人并且不发生overkill的情况下小Q同学才会认为取得了属于他的胜利。

因为小Q同学非常谨慎，他会进行\(10\)次模拟战，每次给出敌人的生命值\(A\)以及overkill的标准\(B\)，他想知道此时取得属于他的胜利的概率是多少，你能帮帮他吗？

格式

输入格式

第一行是一个正整数\(T\)，表示测试数据的组数，

对于每组测试数据，

第一行是两个整数\(X,Y\)，分别表示骰子的面数以及骰子的个数，

接下来\(10\)行，每行包含两个整数\(A,B\)，分别表示敌人的生命值\(A\)以及overkill的标准\(B\)。

输出格式

对于每组测试数据，输出\(10\)行，对每个询问输出一个实数，要求绝对误差不超过\(0.013579\)，

也就是说，记输出为\(a\)，答案为\(b\)，若满足\(|a-b| \leq 0.013579\)，则认为输出是正确的。

本题提供 Special Judge。

样例1

样例输入1

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

样例输出1

0.000002
0.000038
0.000364
0.002213
0.009605
0.031784
0.083534
0.179642
0.323803
0.500000

限制

有 \(10\%\) 的数据，\(X\le 20\)，\(Y\le 40\) 且 \(X^Y \le 10000000\)。

有 \(15\%\) 的数据，\(X\le 20\)，\(Y\le 1600\)。

有 \(30\%\) 的数据，\(X\le 20\)，\(Y\le 8000\)。

有 \(10\%\) 的数据，\(X=2\)，\(Y\le 200000\)。

对于 \(100\%\) 的数据，\(2\le X\le 20\)，\(1\le Y\le 200000\)，\(T \le 10\)，\(0\le A\le B\le (X-1)^Y\) 且 \(Y > 800\) 的数据不超过 2 组。

来源

SDOI 2017 Round2 Day1