题目背景

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

题目描述

然而，这些士兵不一定具有与黑暗势力作战的能力，因而最终被派遣的士兵是未知的

为了尽量了解派遣的士兵的情况，Steve需要你帮忙计算一些值

Steve一共有$t$支军队，每支军队的人数都不同

每支军队可以按一定标准排成$n \times k$的方阵，每个士兵的位置可以用坐标$(x,y)$表示，其中$0\le x < n,0 \le y <k$，这个士兵的编号就是$x\cdot k+y$

位于$(0,0)$位置的士兵是队长，无论任何情况都会被派遣

对于其余的士兵，可以派遣，也可以不派遣

一支$n \times k$的军队的能力值是这样定义的：

如果所有士兵都被派遣，那么能力值是$1$

如果位于$(x,y)$位置的士兵(编号为$i$)未被派遣，那么能力值变为原来的$\frac{x}{i-x}$

例如，对于一支$2\times 2$的军队，如果$(1,1)$位置的士兵(编号为$3$)未被派遣，其他士兵都被派遣，那么能力值为$\frac{1}{3-1}=\frac{1}{2}$

如果$(1,1)$位置的士兵(编号为$3$)和$(0,1)$位置的士兵(编号为$1$)都未被派遣，那么能力值为$\frac{1}{3-1} \times \frac{0}{1-0} = 0$

如果$(1,1)$位置的士兵(编号为$3$)和$(1,0)$位置的士兵(编号为$2$)都未被派遣，那么能力值为$\frac{1}{3-1} \times \frac{1}{2-1} = \frac{1}{2}$

现在，Steve需要你为每一支军队，计算出所有可能派遣方案的能力值之和

为了避免出现分数，输出结果是模$1145141$意义下的值

如果这个值不存在，那么输出$-1$

也就是，如果你的答案为既约分数$\frac{p}{q}$，你需要找到一个最小的非负整数$a$，满足$p\equiv q\cdot a(mod 1145141)$，并输出这个值，如果不存在这样的整数，就输出$-1$

提示：$1145141$是质数

输入格式

第一行一个整数$t$

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

输出格式

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

5
2 2
3 3
1 4
2 4
3 4

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
2	11	100
3	12	100000	5	100000
4	13		100000	5
5	16	5		100000
6	18		$10^9$
7	20	100000

Subtask2包括两个不计分的Hack数据，均满足$t=1$

#8满足#7的性质

#9满足#5的性质