Problem Background

Xiao A is an ordinary high school student, but one day he suddenly got involved in a game of deities. Come help him!

Problem Description

One day, Xiao A was walking home from school when he suddenly encountered two deities, Dreamweaver and Jeremy. They saw Xiao A and immediately proposed a game with him. Surrounded by a golden light, Xiao A agreed to their request without knowing why.

The rules of the game are as follows: The two deities first choose a positive integer \( m \), ensuring that \( m \) is a positive integer power of an odd prime \( p \). Then, they play \( n \) rounds of the game. In each round, Dreamweaver chooses a positive integer \( x \) and Jeremy chooses a positive integer \( y \), ensuring that \( (x, m) = 1 \) and \( (y, m) = 1 \), meaning \( x \) and \( m \) are coprime, and \( y \) and \( m \) are coprime. They then ask Xiao A if there exists a non-negative integer \( a \) such that \( x^a \equiv y \pmod{m} \).

The deities told Xiao A that he could only return to normal life if he answers correctly in every round of the game. In desperation, he had to seek help from a clever you.

Input Format

The first line contains two positive integers \( m \) and \( n \).

The next \( n \) lines, each containing two positive integers \( x \) and \( y \).

Output Format

A total of \( n \) lines, each corresponding to Xiao A's answer in a round of the game.

If such \( a \) exists, the answer is Yes; otherwise, it is No.

Sample Input and Output

Sample Input #1

9 3
1 4
2 1
7 4

Sample Output #1

No
Yes
Yes

Sample Input #2

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

Sample Output #2

Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
No

Notes

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} \).

Data Range

This problem consists of 7 subtasks. You need to pass all test points within a subtask to score points for that subtask.

For all data, \( 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 number chosen uniformly at random from \( [3, 10^{18}] \).

Hints

This problem can use __int128.

见题面 Input 部分

见题面 Output 部分