Floppy Cube 本质上是一个 $1 \times 3 \times 3$ 的魔方。它由 9 个相同的立方体小块组成，排列成一个 $1 \times 3 \times 3$ 的长方体。该拼图由 4 个角块、4 个棱块和 1 个中心块组成。每个角块有 4 种颜色，每个棱块有 3 种颜色，而中心块有 2 种颜色（在相对的面上）。这个拼图可以被看作是围绕其棱块进行旋转。每次旋转会导致一个棱块在原地旋转 180 度，同时两个相邻的角块交换位置（并同时发生旋转）。当然，旋转或翻转整个 Floppy Cube 也是允许的操作。拼图的目标是将其恢复到每个面只有一种颜色的状态。

假设我们希望为 Floppy Cube 贴上新的彩色贴纸，其配色方案不一定是标准的配色。具体来说，我们有 $n$ 种不同的颜色可供选择（每种颜色的贴纸供应无限），并且我们可以在 30 个面上随意放置贴纸。我们不需要使用所有的颜色，如果需要，同一种颜色也可以出现在单个立方体小块的多个面上。

我们称两种配色方案 $c_1$ 和 $c_2$ 是本质不同的，如果根据 $c_1$ 配色的魔方无法通过执行 Floppy Cube 的机械操作变为与根据 $c_2$ 配色的魔方相匹配。在有 $n$ 种不同颜色可供选择的情况下，有多少种本质不同的配色方案？

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 22222$)，表示测试用例的总数。对于每个测试用例，一行包含两个整数 $n$ 和 $P$，其中 $1 \le n, P \le 111111111$。

输出格式

对于每个测试用例，计算在有 $n$ 种不同颜色可供选择的情况下本质不同的配色方案数量，并输出其除以 $P$ 的余数。

样例

输入 1

3
1 32145
2 32145
3 32145

输出 1

1
6738
30690