CERI2018G  Break a cryptosystem
We denote $\varphi$ the Euler's totient function.
The goal of the problem is to crack a message using a simplified RSA cryptosystem.
Here $(n, e)$ denotes the public key, and $c$ a crypted message.
Input
The first line of the input consist of a single integer number t which determines the number of tests.
In each of next t lines there is three integer numbers n, e and c.
Constraints
 0 < t ≤ 10 000
 0 < n ≤ 100 000 000, is the product of two distinct prime numbers (p, q)
 0 < e ≤ 100 000 000, is coprime with $\varphi(n)$
 0 ≤ c < n
Output
Print $m$ such that
 the result of $m^e$ modulo $n$ is equal to $c$ ;
 $0\leq m < n$.
Example
Input: 1 55 7 18 Output: 2
hide comments
[Lakshman]:
20180507 21:47:07
Is it not an easy problem?


wisfaq:
20180507 13:23:46
brake(english) means freiner (french)

Added by:  Francky 
Date:  20180503 
Time limit:  1s20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 