Warning: This problem looks like, but differs from GCD3 :
GCD3 : (2^K-2) ---vs--- GCD4 : (2K-2)
Moreover, your challenge will be to shorten your code to get more points.
GCD4 could be harder than GCD3!

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given three integers N, M and K such that:
N = a + b
M = a² + b² - (2K-2)×a×b
with a > 0, b > 0 and gcd(a, b) = 1.

Output

For each test case, you have to print gcd(N, M), the greatest common divisor.

Example

Input:
2
2214811 1451126169481 7
107603 9066347749 9

Output:
1
1

Note: For the first trio a = 117651 and b = 2097160.
For the second a = 1313 and b = 106290.

Constraints

0 < T < 14321
0 < N < 10^200
1 < M < 10^200
0 < K < 17

For your information, my 293B C code get AC in 0.03s with 1.6MB of memory print.
Size code limit will be 666B.
Language restrictions are quite the same than in GCD3, and it is justified ;-)
Have fun ;-)