GCD4  Discrete Math Problem (shorten)
Warning: This problem looks like, but differs from GCD3 :
GCD3 : (2^{K}2) vs
GCD4 : (2K2)
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^{2} + b^{2}  (2K2)×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 ;)
hide comments
Francky:
20170212 01:51:36
Some languages were added. Ask for Rust or Dart, or ??? If need, as long as there's no integrated bignum library. 

Linghui Liu:
20140621 03:23:36
@mitchs, thanks very much. 

Mitch Schwartz:
20140621 00:32:53
@Linghui Liu: Congrats! For this and the other numerous records you've recently taken. :p 

Linghui Liu:
20131123 03:59:48
@Mitch Schwartz Sorry for the spoiler, thanks for the comment. I still can't get the first case AC, but I use the same function.


Mitch Schwartz:
20131121 05:41:39
@Linghui Liu: I've hidden your comment because of spoilers. It is still visible to Francky and some others. Regarding your question, you must have some bug in the first case, and in the second case you've made a math error. (You could easily find a counterexample by randomly generating some cases.) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140429 22:05:56
@Michael Kharitonov: If K is arround 10^200, then K will be useless information. better to compute gcd(M,N) directly. (Correct Me If I'm Wrong)


Michael Kharitonov:
20130511 20:31:51
Last edit: 20130514 20:30:38 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130511 10:39:03
easy points, thanks :) 

Aditya Pande:
20130505 05:50:33
i just don't get what Mitch is doing? incredible...:)

Added by:  Francky 
Date:  20130503 
Time limit:  1s 
Source limit:  666B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  CCLANG C C++ 4.3.2 CPP CPP14 CPP14CLANG C99 DCLANG D FORTRAN PASGPC PASFPC 
Resource:  GCD3 