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