Discrete Logarithm Existence on Prime Power Modulo

One day, Little A was walking home from school when he suddenly met two dream makers and Jeremy. Upon seeing Little A, they proposed a game. Enchanted by a golden light, Little A reluctantly agreed. The rules of the game are as follows:

First, the two dream makers choose a positive integer \(m\), which is a positive integer power of an odd prime \(p\) (i.e. \(m=p^k\) for some \(k \ge 1\)). Then they play \(n\) rounds. In each round, the first participant chooses a positive integer \(x\) and Jeremy chooses a positive integer \(y\), with the constraint that \(\gcd(x, m) = 1\) and \(\gcd(y, m) = 1\). Little A must then determine if there exists a nonnegative integer \(a\) such that \[ x^a \equiv y \pmod{m}. \]

If Little A answers correctly in every round, he will be allowed to return to a normal life. Can you help him by writing a program to answer their queries?

inputFormat

The first line contains two positive integers \(m\) and \(n\), where \(m\) is an odd prime power (i.e. \(m=p^k\) for some odd prime \(p\) and integer \(k \ge 1\)) and \(n\) is the number of rounds.

Each of the following \(n\) lines contains two integers \(x\) and \(y\) (\(1 \le x, y < m\)), both coprime with \(m\) (i.e. \(\gcd(x,m)=1\) and \(\gcd(y,m)=1\)).

outputFormat

For each round, output a single line containing YES if there exists a nonnegative integer \(a\) such that \(x^a \equiv y \pmod{m}\), otherwise output NO.

sample

7 3
3 2
2 4
2 3

YES
YES
NO