- Practice
- Mathematics
- Number Theory
- Little Panda Power

# Little Panda Power

# Little Panda Power

**Little Panda** has a thing for powers and modulus and he likes challenges. His friend **Lucy**, however, is impractical and challenges **Panda** to find both positive and negative powers of a number modulo a particular number. We all know that refers to the modular inverse of modulo (see Wikipedia).

Since **Lucy** is impractical, she says that for .

Now she wants **Panda** to compute .

She also thinks that this problem can be very difficult if the constraints aren't given properly. **Little Panda** is very confused and leaves the problem to the worthy programmers of the world. Help him in finding the solution.

**Input Format**

The first line contains , the number of test cases.

Then lines follow, each line containing , and .

**Output Format**

Output the value of .

**Constraints**

and are coprime to each other (see Wikipedia)

**Sample Input**

```
3
1 2 3
3 4 2
4 -1 5
```

**Sample Output**

```
1
1
4
```

**Explanation**

*Case 1:*

*Case 2:*

*Case 3:*