P5605 小 A 与两位神仙

小 A 是一个普普通通的高中生，但是他某一天忽然被卷入了神仙的游戏中，快来帮帮他！

某一天，小 A 正走在放学回家的路上，忽然遇见了两个神仙造梦者和杰瑞米，祂们一看到小 A 就说要和小 A 玩游戏，小 A 被笼罩在金光中，莫名其妙就答应了祂们的要求。 这个游戏的规则是这样的：两个神仙先选定一个正整数 $m$，保证 $m$ 是一个奇质数 $p$ 的正整数次幂。然后进行 $n$ 轮游戏，每轮中造梦者选定一个正整数 $x$，杰瑞米选定一个正整数 $y$，保证 $(x, m) = 1, (y, m) = 1$，即 $x$ 与 $m$ 互质，$y$ 与 $m$ 互质，接下来询问小 A 是否存在非负整数 $a$ 使得 $x^a \equiv y \pmod{m}$。 神仙们说小 A 只有在每一轮游戏中都回答正确才能回到正常的生活中，不得已之下他只好求助于聪明的你。

无

无

**样例解释** $1^a \equiv 1 \not \equiv 4 \pmod {9}$。 $2^6 \equiv 64 \equiv 1 \pmod {9}$。 $7^2 \equiv 49 \equiv 4 \pmod {9}$。 **数据范围** 本题共 $7$ 个子任务，你需要通过一个子任务内的所有测试点才能取得这个子任务的分数。 对于所有数据满足 $1\le n\le 2\times 10^4$，$3\le m \le 10^{18}$，$1 \le x, y < m$ 。 | # | 分数 | $n$ | $m$ | 特殊性质1 | 时间限制 | | ---- | ---- | ------------------------ | ------------------- | --------- | --------- | | 1 | 3 | $\le 5$ | $\le 10^6$ | × | 1s | | 2 | 37 | $\le 5$ | $\le 10^9$ | × | 1s | | 3 | 22 | $= 1$ | $\le 10^{18}$ | × | 1s | | 4 | 13 | $\le 100$ | $\le 10^{18}$ | √ | 1s | | 5 | 10 | $\le 100$ | $\le 10^{18}$ | × | 1s | | 6 | 5 | $\le 2000$ | $\le 10^{18}$ | × | 1s | | 7 | 10 | $\le 2\times 10^4$ | $\le 10^{18}$ | × | 3s | 特殊性质1：令 $m = p^{a}$，则 $p$ 是在 $[3, 10^{18}]$ 等概率选取的一个素数。 **提示** 本题可以使用 `__int128`。