The RSA problem is the following: given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e, (p - 1) · (q - 1)) = 1, and an integer c, find an integer m such that me = c (mod n).

Input

The first line contains the number of test cases k (k ≤ 2000). Each next line is a separate test case, that contains three positive integer numbers e, n and c (e, n, c ≤ 32000, n = p · q; p, q - distinct odd primes, gcd(e, (p - 1) · (q - 1)) = 1, e < (p - 1) · (q - 1)).

Output

For each test case print in a separate line the encrypted integer m.