P17626 多首的怪物

睦是多首的怪物，所以睦自然也需要很多条项链。 睦有 $n$ 个互不相同的珠子，她现在要将它们串成若干条项链，戴在自己的各个脑袋上。因为脑袋的大小都差不多，所以每一条项链都要恰好有 $m$ 个珠子。珠子必须用完。 睦想知道有几个不同的串项链的方案，她只需要你告诉她答案对 $m$ 取模的值就好了。 两个项链不同当且仅当不可以通过旋转一个项链使其变为另一个项链。 且睦不关心项链间的顺序，也就是说一种方案重排项链的顺序不记为新方案。

**本题有多组测试数据。** 第一行，一个数 $T$，表示数据组数。 接下来 $T$ 行，每行两个数 $n$ 和 $m$，表示珠子的个数和每个项链的珠子数。

对于每组数据，输出一行，一个整数，表示方案数对 $m$ 取模的值。

#### 样例解释： 对于第一组数据：$n=4,m=4$，只能串成一条项链，有 $6$ 种方案 $(1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2),(1,4,2,3),(1,4,3,2)$。故而输出 $2$。 可以证明不包含其他方案，例如 $(2,4,3,1)$ 可以通过旋转 $(1,2,4,3)$ 得到。 对于第二组数据：因为 $m=1$，所以取模后答案一定为 $0$。 对于第三组数据：珠子不可能用完，所以答案为 $0$。 --- #### 数据范围： **本题目采用子任务捆绑测试。** 对于所有数据：$1 \le n \le 10^{18}$，$1 \le m \le 10^{10}$，$1 \le T \le 2000$。 ::cute-table{tuack} | 子任务编号 | $n\le$ | $m\le$ | $T\le$ |特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:|:-:| | $0$ | $5$ | $5$ | $50$ | 无 | $15$ | | $1$ | $3000$ | $3000$ | ^ | ^ | $5$ | | $2$ | $10^5$ | $10^5$ | ^ | ^ | $10$ | | $3$ | $10^9$ | ^ | ^ | ^ | $5$ | | $4$ | $10^{16}$ | $10^9$ | $500$ | A | $20$ | | $5$ | ^ | ^ | ^ | B | ^ | | $6$ | ^ | ^ | $2000$ | C | $5$ | | $7$ | $10^{18}$ | $10^{10}$ | ^ | 无 | $20$ | 特殊性质 A：保证 $n$ 是奇数。 特殊性质 B：保证 $m$ 是质数。 特殊性质 C：保证数据随机生成。具体的，$n$ 在 $[1,10^{16}]$ 的所有整数中等概率随机选取，$m$ 在 $[1,10^9]$ 的所有整数中等概率随机选取。