e-olymp
Competitions

DSLCS 2011 Number Theory. Favorites

RSA Attack

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 (k2000). Each next line is a separate test case, that contains three positive integer numbers e, n and c (e, n, c32000, 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
9 187 129
11 221 56
7 391 204
Output example #1
7
23
17