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