CERI2018F - Encrypt a message


We denote $\varphi$ the Euler's totient function.

The goal of the problem is to send a message using a simplified RSA cryptosystem.

Here $(n, e)$ denotes the public key, and $m$ a message to be encrypted.

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 m.

Constraints

  • 0 < t ≤ 100 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)$
  • 1 < m ≤ n

Output

Print the result of $m^e$ modulo $n$, that is the encrypted message.

Example

Input:
1
55 7 2
Output:
18


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