Description

One day, Little A was walking home after school when he suddenly met two immortal dream-makers, Zaomengzhe and Jeremy. As soon as they saw Little A, they said they wanted to play a game with him. Little A was covered in golden light and, for some reason, agreed to their request.

The rules of the game are as follows: the two immortals first choose a positive integer $m$, and guarantee that $m$ is a positive integer power of an odd prime $p$. Then they play $n$ rounds. In each round, Zaomengzhe chooses a positive integer $x$, and Jeremy chooses a positive integer $y$, with $(x, m) = 1$ and $(y, m) = 1$, meaning $x$ is coprime to $m$ and $y$ is coprime to $m$. Then they ask Little A whether there exists a non-negative integer $a$ such that $x^a \equiv y \pmod{m}$.

The immortals say that only if Little A answers correctly in every round can he return to normal life. With no other choice, he asks you, the smart one, for help.

Input Format

The first line contains two positive integers $m, n$.

The next $n$ lines each contain two positive integers $x, y$.

Output Format

Output a total of $n$ lines, each corresponding to Little A's answer for one round.

If it exists, output Yes; otherwise, output 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

Hint

Sample Explanation

$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}$.

Constraints

This problem has $7$ subtasks. You must pass all test points within a subtask to obtain the score for that subtask.

For all testdata, $1\le n\le 2\times 10^4$, $3\le m \le 10^{18}$, $1 \le x, y < m$.

Special Property 1: Let $m = p^{a}$. Then $p$ is a prime chosen uniformly at random from $[3, 10^{18}]$.

Hint

You may use __int128.

Translated by ChatGPT 5