题目背景

小 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 只有在每一轮游戏中都回答正确才能回到正常的生活中，不得已之下他只好求助于聪明的你。

输入格式

第一行两个正整数 $m, n$。

接下来 $n$ 行，每行两个正整数 $x, y$。

输出格式

一共 $n$ 行，每行对应一轮游戏中小 A 的回答。

如果存在，那么答案为 Yes，否则为 No。

9 3
1 4
2 1
7 4

No
Yes
Yes

29788562298698657 10
4623623705787050 4128735493476588
29371111781967946 19402395181570597
23313713550468151 18155134012955455
654639695903289 323875358727922
15727861955653242 26658913688488667
10815360622718474 4625834559167483
10836636083182170 10347869939717751
8972909638986721 1887397472131862
23442032136521081 29735793306181382
325363900801763 6960017105353559

Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
No

提示

样例解释

$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$ 。

特殊性质1：令 $m = p^{a}$，则 $p$ 是在 $[3, 10^{18}]$ 等概率选取的一个素数。

提示

本题可以使用 __int128。