Given integers A, B and N, you should calculate the GCD of A^N+B^N and |A−B|. (Assume that GCD(0,a)=a for any positive integer a). Since this number could be very large, compute it modulo 1000000007 (10^9+7).

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first and only line of each test case contains three space-separated integers A, B and N.

Output

For each test case, print a single line containing one integer — the required GCD modulo 10^9+7.

Constraints

1≤T≤10

1≤A,B,N≤1012

B≤A

Can anyone please give me the idea to solve this problem ??

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first and only line of each test case contains three space-separated integers A, B and N.

Output

For each test case, print a single line containing one integer — the required GCD modulo 10^9+7.

Constraints

1≤T≤10

1≤A,B,N≤1012

B≤A

Can anyone please give me the idea to solve this problem ??

Registered users can post here. Sign in or register to post.