RSA Attack#1561
The RSA problem is as follows: given a positive integer that is a product of two distinct odd primes and , a positive integer such that \gcd(e, (p - 1) \cdot (q - 1)) = 1, and an integer , find an integer such that m^e \equiv c \pmod{n}.
The first line contains the number of test cases (k \leq 2000). Each of the following lines contains a separate test case, with three positive integers , , and (e, n, c \leq 32000; n = p \cdot q; , are distinct odd primes; \gcd(e, (p - 1) \cdot (q - 1)) = 1; e < (p - 1) \cdot (q - 1)).
For each test case, print in a separate line the integer .
Example 1