VGCD - The Very Greatest Common Divisor


Given two integers a and b find their greatest common divisor.

Input

The first line of the input file contains number 0 < n < 1000 the amount of tests. The description of n test cases follow. The description of a test case consists of two lines. The first line contains integer a (0 < a < 10^12540), the second – integer b (0 < b < 10^12540). It is also known that all the numbers in the input file are the determinants of the square matrix of the form:

Output

For each test case print the greatest common divisor of integers a and b on a separate line.

Example

Input:
3
2
3
3
21
6765
610

Output:
1
3
5

hide comments
mahmud2690: 2017-03-28 20:17:52

stupid input format

Bhuvnesh Jain: 2015-11-17 12:53:50

image is not visible

=(Francky)=> Fixed.

Last edit: 2015-11-17 19:07:43
codershinchan: 2015-09-07 05:42:05

image is not visible

Soma: 2015-06-20 16:11:39

can some tell me how to optimize my code? i have been getting TLE. code: http://ideone.com/LyRU2S

Last edit: 2015-06-20 16:13:41
Andrey Maksimenko: 2013-12-18 11:32:17

How to avoid NZEC in python for such testdata?

aristofanis: 2012-11-03 17:29:41

what is the NZEC runtime error?

numerix: 2011-01-12 20:28:18

There is no problem reading the input with Python.

Vladimir Kirichenkoff: 2011-01-10 01:29:57

I don't know if spaces were my problem (python), but i've finally got AC using C++

ymGXX: 2010-11-18 02:21:46

nice problem!

Vladimir Kirichenkoff: 2010-08-19 18:29:21

Spooky, remove the spaces from the tests, pls!

Last edit: 2010-08-20 00:07:18

Added by:Spooky
Date:2010-04-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Open All-Ukrainian Collegiate Contest Semi-Final, 2010