## 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
 < Previous 1 2 3 4 5 6 7 8 9 10 Next > mafia_987: 2023-04-08 21:58:55 make cases if a==0 return b else first calculate b%a and finally take gcd with a.really very easy problem just have to think of this intuition kumar_anubhav: 2020-06-14 11:24:21 Nice Ques with basic Division Mathematics :) AC !! this_variable: 2020-06-01 07:33:15 No java :( dreamanddead: 2020-05-12 10:18:35 1000 Bytes for cpp, how to do that? darker__space: 2020-01-21 13:56:42 if u r doing brute force then think another short trick or method...for sure it exists roni_roy18: 2019-06-01 08:57:44 So easy using string in cpp :) AC in one go, also in 0.00 sec :) Last edit: 2019-06-01 08:58:41 sea_26: 2018-11-26 18:45:17 Very easy with string in cpp.If you use char array size then fixed 252 because 10^250. malcolm123_ssj: 2018-11-17 18:54:59 don't think much. use python to solve such questions prachij: 2018-10-03 20:57:34 AC in one go in Python 3 with 4 lines of code :D mynk322: 2018-09-19 15:41:38 REMEMBER!!!! gcd of a,0 is a. gcd of 0,b is b. cost me 2 WA!!

 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 PERL PERL6 PHP PYTHON RUBY VB.NET Resource: My own Resource