## 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
 zai zai: 2014-03-25 12:08:03 @Narendra yadav: thank you Narendra yadav: 2014-02-05 00:31:07 Output Of 0 0 is 0. costed me many WA. appy: 2014-01-18 21:18:38 what is the output of 0 0 and output of 0 n reply asap Last edit: 2014-02-17 18:59:38 appy: 2014-01-11 17:13:54 can any1 explain runtime error(SIGFPE) VIVEK GARG: 2013-09-12 07:09:22 just think that in first step how to calculate reminder . pika_pika: 2013-07-16 09:04:23 @yyf thanks for the case #a=0. got several SIGPFE for that and a WA. Finally AC Prakhar Gupta: 2013-07-08 11:04:50 can u give some more test cases... mystique_blue: 2013-06-19 08:48:49 Please enable python 2.7 as well. #vaidy_MIT#: 2013-04-02 05:10:41 @ sridharan Use (int,string:char array !!) Sridharan Ramachandran: 2013-03-28 09:51:07 Which is the best data type to use in c++ for storing numbers in that (0 <= A <= 40000 and A <= B < 10^250)

 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