Competitions

# DSLCS 2011 Number Theory. Favorites

# RSA Attack

The RSA problem is the following: given a positive integer **n** that is a product of two distinct odd primes **p** and **q**, a positive integer **e** such that **gcd**(**e**, (**p** - **1**) · (**q** - **1**)) = **1**, and an integer **c**, find an integer **m** such that `m`

= ^{e}**c** (mod **n**).

#### Input

The first line contains the number of test cases **k** (**k** ≤ **2000**). Each next line is a separate test case, that contains three positive integer numbers **e**, **n** and **c** (**e**, **n**, **c** ≤ **32000**, **n** = **p** · **q**; **p**, **q** - distinct odd primes, **gcd**(**e**, (**p** - **1**) · (**q** - **1**)) = **1**, **e** < (**p** - **1**) · (**q** - **1**)).

#### Output

For each test case print in a separate line the encrypted integer **m**.

Input example #1

3 9 187 129 11 221 56 7 391 204

Output example #1

7 23 17