## 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 2Output:18

Added by: | Francky |

Date: | 2018-05-03 |

Time limit: | 1s-5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |