## GCD2 - GCD2

Frank explained its friend Felman the algorithm of Euclides to calculate the GCD of two numbers. Then Felman implements it algorithm

```int gcd(int a, int b)
{
if (b==0)
return a;
else
return gcd(b,a%b);
}
```
and it proposes to Frank that makes it but with a little integer and another integer that has up to 250 digits.

Your task is to help Frank programming an efficient code for the challenge of Felman.

### Input

The first line of the input file contains a number representing the number of lines to follow. Each line consists of two number A and B (0 <= A <= 40000 and A <= B < 10^250).

### Output

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

### Example

```Input:
2
2 6
10 11

Output:
2
1```

Source limit is 1,000 Bytes.

hide comments
 അഭി : 2014-10-14 12:14:38 Keep getting internal error. lang=pypy, id=12623106 SHIVAM DIXIT: 2014-09-28 13:07:32 be careful of follwing test cases 0 0 ->0 0 10 ->10 10 0 ->10 Last edit: 2014-09-28 13:07:49 ISHANI: 2014-09-18 16:58:02 after doing this,see this problem http://www.spoj.com/problems/GCD3/ Rajat (1307086): 2014-08-17 22:58:26 half of code is already solved in ques..... thing is how to reduce code to that level rahul nagurtha: 2014-07-25 18:35:02 please enable python 2.7 `Ak: 2014-06-29 07:27:14 1 0 0 output 0 costed me 1 runtime error(SIGFPE) Sumit Mishra: 2014-06-06 20:20:12 getting WA http://ideone.com/nEnAMz agaurav77: 2014-06-06 17:15:10 Here, interpreted languages do better than compiled ones. Euclid's algo works in these languages. pvkcse: 2014-05-20 19:52:25 fractions.gcd() got TLE but euclid works fine and got AC with 0.10s in python... Arpit Uppal: 2014-04-26 06:42:13 easy one... my 250th classical problem on spoj :)

 Added by: Frank Rafael Arteaga Date: 2008-08-04 Time limit: 1s Source limit: 1000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: C99 LISP sbcl LISP clisp ERL JAVA JS-RHINO NODEJS PERL6 PERL PHP PYTHON RUBY VB.NET Resource: My own Resource