GCD3 - Discrete Math Problem

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 following 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 5
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
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS D ERL FORTRAN ICON ICK JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PRLG-swi SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:Discrete Math

hide comments
2009-10-25 16:50:20 Muhammad Ridowan
The page is really wide. For the wide input.
2009-10-25 16:50:20 Brian Bi
"Note: For the first trio a = 648570884104668119354126 y b = 7"

"y" means "and", right? (psetter is evidently a Spanish-speaker)
2009-10-25 16:50:20 Brian Bi
Is it just me, or is this page way too wide?
2009-11-30 21:10:59 Frank Rafael Arteaga
yeah, sorry. I work on it.
2009-10-25 16:50:20 [Trichromatic] XilinX
Mmm, something is wrong with the input file. I think now the input file is empty :-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.