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$.
That is the decrypted message. You have to break this cryptosystem !

Example

Input:
1
55 7 18
Output:
2

hide comments
[Lakshman]: 2018-05-07 21:47:07

Is it not an easy problem?
=(Francky)=> True, it's not an easy one ; but it might already exists on SPOJ classical. If not, I'll move it to classical ; or create a real 'classical' one.

Last edit: 2018-05-07 22:19:37
wisfaq: 2018-05-07 13:23:46

brake(english) means freiner (french)
I think you mean 'break'.
=(Francky)=> Oui, merci beaucoup. Corrigé ;-)

Last edit: 2018-05-07 15:27:26

Added by:Francky
Date:2018-05-03
Time limit:1s-20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All