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⁸

F(n) ≤ 10¹⁸

M ≤ 100

mod = 10000000000283

Example

Input:
1
6 50 3

Output:
0