派遣

题目背景

Steve在洞穴里发现了一张地图,上面标识出了黑暗势力的据点,他决定派遣一些士兵前去

题目描述

然而,这些士兵不一定具有与黑暗势力作战的能力,因而最终被派遣的士兵是未知的 为了尽量了解派遣的士兵的情况,Steve需要你帮忙计算一些值 Steve一共有$t$支军队,每支军队的人数都不同 每支军队可以按一定标准排成$n \times k$的方阵,每个士兵的位置可以用坐标$(x,y)$表示,其中$0\le x < n,0 \le y

输入输出格式

输入格式


第一行一个整数$t$ 接下来$t$行,每行两个整数$n,k$

输出格式


$t$行,每行一个整数表示答案

输入输出样例

输入样例 #1

5
2 2
3 3
1 4
2 4
3 4

输出样例 #1

3
7
1
381716
127244

说明

第四组数据实际值为$\frac{7}{3}$ 第五组数据实际值为$\frac{55}{9}$ 第一组数据解释: 如果所有士兵都被派遣,那么能力值为$1$ 如果$(1,1)$位置的士兵(编号为$3$)未被派遣,那么能力值为$\frac{1}{3-1}=0.5$ 如果$(0,1)$位置的士兵(编号为$1$)未被派遣,那么能力值为$\frac{0}{1-0} = 0$ 如果$(1,1)$位置的士兵(编号为$3$)和$(0,1)$位置的士兵(编号为$1$)未被派遣,那么能力值为$\frac{1}{3-1} \times \frac{0}{1-0} = 0$ 如果$(1,0)$位置的士兵(编号为$2$)未被派遣,那么能力值为$\frac{1}{2-1} = 1$ 如果$(1,0)$位置的士兵(编号为$2$)和$(1,1)$位置的士兵(编号为$3$)未被派遣,那么能力值为$\frac{1}{2-1} \times \frac{1}{3-1}=0.5$ 如果$(1,0)$位置的士兵(编号为$2$)和$(0,1)$位置的士兵(编号为$1$)未被派遣,那么能力值为$\frac{1}{2-1} \times \frac{0}{1-0}=0$ 如果只有队长被派遣,那么能力值为$\frac{1}{3-1} \times \frac{0}{1-0} \times \frac{1}{2-1}=0$ 所以,答案为$1+0.5+0+0+1+0.5+0+0=3$ 数据范围: 对于所有数据,$n\ge 1,k\ge 2$ Subtask1是比赛时的测试数据: 测试点| 分值| t | $n\le$| $k\le$ :-: | :-: | :-: | :-: | :-: 1| 10| 5| 5| 5| 2| 11| 100| 100| 100| 3| 12| 100000| 5| 100000| 4| 13| 100000| 100000| 5| 5| 16| 5| 100000| 100000| 6| 18| 5| $10^9$| $10^9$| 7| 20| 100000| $10^9$|$10^9$| Subtask2包括两个不计分的Hack数据,均满足$t=1$ #8满足#7的性质 #9满足#5的性质