SP5084 GCD3 - Discrete Math Problem

Given $N, M$ and $K$ ($1 \le N$, $M \le 100^{200}$ and $1 \le K \le 16$) which - $N = a + b$ - $M = a^2 + b^2 - (2^K - 2) \times a \times b$ with $a > 0$, $b > 0$ and $\gcd(a, b) = 1$. Your task is to find $\gcd(N, M)$.

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

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

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