该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

一只羊在研究一座古老的旋转色轮法阵。

法阵由一个中心圆盘和外侧的一圈环形区域组成。环形区域被等角度地分成了 $M$ 个扇形小块，因此整个法阵一共包含 $M+1$ 个区域。

题目描述

现在，一只羊想用 $N$ 种颜色给这座法阵染色。

设中心区域编号为 $0$ ，外侧的 $M$ 个扇形区域按顺时针方向依次编号为 $1,2,\dots,M$ 。如果两个区域有长度非零的公共边界，则称它们相邻。于是：

中心区域 $0$ 与所有外侧区域都相邻；
对于任意 $1\le i\le M$ ，区域 $i$ 与区域 $i-1$ 和区域 $i+1$ 相邻，其中下标对 $M$ 取模，即区域 $1$ 与区域 $M$ 也相邻。

要求任意两个相邻区域的颜色均不相同。

如果两种染色方案能够通过将整个法阵绕圆心旋转若干个整扇形角度后完全重合，则认为这两种方案是同一种方案。

现在给定 $T$ 组询问，请你对每组给出的 $N,M$ ，求出本质不同的合法染色方案数。

由于答案可能很大，你只需要输出答案对模数

P=2305843009213693951

取模后的结果。

不难发现，它是素数。

第一行一个整数 $T$ ，表示询问组数。

接下来 $T$ 行，每行两个整数 $N,M$ ，分别表示颜色种数和外侧扇形区域数。

输出 $T$ 行，每行一个整数，表示对应询问的答案对模数 $P$ 取模后的结果。

测试点编号	分值	$T$ 上限	$N$ 上限	$M$ 上限
1	5	$1$	$4$	$6$
2		$2$	$4$	$7$
3		$3$	$5$	$8$
4		$3$	$6$	$8$
5		$10$	$10^9$	$10^4$
6		$10$	$10^9$	$5\times 10^4$
7		$15$	$10^{12}$	$10^5$
8		$15$	$10^{12}$	$2\times 10^5$
9		$20$	$10^{18}$	$10^6$
10				$10^7$
11				$10^8$
12				$10^9$
13		$30$		$10^{10}$
14				$10^{11}$
15				$10^{12}$
16				$10^{13}$
17		$40$		$10^{14}$
18		$40$		$10^{16}$
19		$50$		$10^{17}$
20		$50$		$10^{18}$