## DCEPC200 - The Prime Minister

no tags

DCE Coders mentors got fed up by making problems, they are deciding upon the toughest problem for contest. Everybody started to tease Ankur sir that he can’t make a single tough problem for juniors. He got very angry, now you only handle Ankur sir’s anger (Beware: All the tough number theory problems given to you as assignments are like 2+2=4 for Ankur sir). Here is the problem given by him (Say thanks to Jyoti ma’am that she softens the problem slightly.. ;)). You are given an integer n.  There will be 2 different numbers K1 and K2, such that K1*K2 = n.

Both of which satisfies the equation  (Totient(K!)  mod K) !=0.

You are also given value of a function, F(n) = Sum of squares  of factor of n. (example F(20) = 546)

Now you have to calculate the value of x and y which satisfies the equation K1x + K2y = m. Where m is given. Since there are many roots you have to find a single pair (x,y) which satisfies the equation having minimum absolute value of (x +y). If no pair is possible output -1. Else output (abs(x+y)^m)%mod

### Input

First line contains T(1<=T<=10000) number of test cases. Each test case consist of single line containing 3 integers n, F(n) and m.

### Output

Output  T lines , each line contains a single integer ((x+y)^m)%mod.

### Constraints

T<=10000

N<=10^8

F(n)<=10^18

M<=100

mod=10000000000283

### Example

```Input:
1```
```6 50 3

Output:
0 ```