题目描述

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

假设我们想给一个 Floppy Cube 贴上新的颜色贴纸，采用的配色方案不必是标准配色。具体地，我们有 $n$ 种不同的颜色可用（每种颜色的贴纸数量不限），我们以任意方式在 30 个面上各贴一张贴纸。并不要求用到所有颜色，如果愿意，同一种颜色可以出现在同一个立方体块的多个面上。

我们说两种这样的涂色方案 $c_1$ 和 $c_2$ 是 本质不同 的，如果通过机械上可行的 Floppy Cube 转动，无法使按 $c_1$ 着色的魔方与按 $c_2$ 着色的魔方相吻合。问当有 $n$ 种不同颜色可用时，本质不同的涂色方案有多少种？

输入格式

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

输出格式

对于每个测试用例，计算当有 $n$ 种不同颜色可用时本质不同涂色方案的数量，并输出该数量除以 $P$ 所得的余数。

3
1 32145
2 32145
3 32145

1
6738
30690

提示

翻译由 DeepSeek V4 Pro 完成