SPOJ Problem Set (classical) 5084. Discrete Math Problem Problem code: GCD3

Given N, M and K (1 <= N, M <= 100^200 and 1 <= K <= 16) which

N = a + b
M = a^2 + b^2 - (2^K - 2) * a * b

with a > 0, b > 0 and gcd(a, b) = 1.

Your task is to find gcd(N, M).

Input

The input file consists of several data sets. The first line contains
the number of data sets T (1 <= T <= 10000). The fallowing T lines
describe the data sets, one triple (N, M, K) for each.

Output

For each data test in the input write the gcd(N, M).

Example

Input:

2
648570884104668119354133 420644191708310845403065233058235585438328857465 10
8017723549 59173349743176010825 9

Output:

1
1

Note: For the first trio a = 648570884104668119354126 and b = 7.
For the second a = 8016478423 and b = 1245126.

---

Added by:	Frank Rafael Arteaga
Date:	2009-10-24
Time limit:	0.100s-0.300s
Source limit:	1000B
Languages:	All except: C++ 4.3.2 CLOJ LISP clisp LISP sbcl F# GO HASK JAVA PERL 6 PHP PIKE PYTH 2.5 PYTH 3.1.2 RUBY TECS
Resource:	Discrete Math