Ivan the Terrible P36895

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⁹, 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.