Ivan the Terrible P36895

Given three integer numbers $n$, $a$ and $b$, does there exist a natural $t$ such that $a^t \equiv b \bmod n$?

Input

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

Output

For each case, print “YES” or “NO” depending on whether $a^t \equiv b \bmod n$ has at least one solution $t \ge 0$ or not.