Given three integer numbers n, a and b,
does there exist a natural t such that a^{t} ≡ b modn?

Input

Input consists of the number of cases c,
followed by c triples with n, a and b.
You can assume
2 ≤ n ≤ 10^{9},
0 ≤ a < n,
and 0 ≤ b < n.
Additionally,
assume c ≤ 200
for the “hard private test cases”.

Output

For each case,
print “YES” or “NO”
depending on whether a^{t} ≡ b modn has at least one solution t ≥ 0 or not.

Public test cases

**Input**

7 2 1 0 7 3 6 8 3 6 6 0 5 6 0 1 1000000000 42424242 1 1000000000 123456789 987654320

**Output**

NO YES NO NO YES YES NO

Information

- Author
- Ivan Geffner
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Quinzè Concurs de Programació de la UPC - Semifinal
- Date
- 2017-06-29