SP8063 AMR10I - Dividing Stones

有 $N$ 块石头，可以任意分成若干堆。每种分法的价值是所有堆中石头数量的乘积对 $P$ 取模后的结果。对于特定的 $N$ 和 $P$，可能出现多少种不同的价值？

第一行是测试用例的数量 $T$。接下来的 $T$ 行中，每行提供两个整数，分别表示一个测试用例的 $N$ 和 $P$。

输出 $T$ 行，每行给出对应测试用例的答案。

- $T \le 20$ - $2 \le N \le 70$ - $2 \le P \le 10^9$ **样例输入** ``` 2 3 1000 5 1000 ``` **样例输出** ``` 3 6 ``` **解释** 对于第一个测试用例，石头可以按以下方式分堆：(1,1,1)，(1,2)，(2,1)，(3)；其值分别为 1，2，2，3，所以有 3 种不同的值。 对于第二个测试用例，可能的价值是数字 1 到 6，以下是计算过程： 1 = 1 \* 1 \* 1 \* 1 \* 1 2 = 2 \* 1 \* 1 \* 1 3 = 3 \* 1 \* 1 4 = 4 \* 1 5 = 5 6 = 2 \* 3 **本翻译由 AI 自动生成**