## 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```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````def gcd(a, b):
while a > 0 and b > 0:
if a >= b:
a %= b
else:
b %= a
return a + b

T = int(input())
for i in range(T):
a, b = map(int, raw_input().split())
print(gcd(a, b))``````
Copy The Code &

Input

cmd
2
2 6
10 11

Output

cmd
2
1

### #2 Code Example with Java Programming

```Code - Java Programming```

``````import java.io.BufferedReader;
import java.io.IOException;
import java.math.BigInteger;
import java.util.Random;

public class GCD2 {

public static void main(String[] args) throws IOException {
while (N-- > 0) {
Integer A = Integer.parseInt(temp[0]);
BigInteger B = new BigInteger(temp[1]);
if(A.equals(0)){
System.out.println("0");
continue;
}

Random randomGenerator = new Random();
while (true) {
Integer bb = B.mod(new BigInteger(A+"")).intValue();
long gcd1 = (gcd1(A, bb));

if(gcd1 != gcd2){
System.out.println(A+" " +bb);
System.out.println("gcd1 "+gcd1);
System.out.println("gcd2 "+gcd2);
break;
}
else{
System.out.println("PASS "+A+" "+B);
}
A = randomGenerator.nextInt(10000000);
B = new BigInteger(randomGenerator.nextInt(10000000)+"");
}

}

}

static int gcd1(int a, int b)
{
if (b==0)
return a;
else
return gcd1(b,a%b);
}

static long specialMode(String big,long small){
long remainder = 0;
for (int index = 0; index < big.length(); index++){
if(remainder >= small){
remainder = remainder % small;
}
remainder = remainder * 10;
remainder +=  Integer.parseInt(big.charAt(index)+ "");

}
return remainder % small;
}

static long gcd2(long A,long B){
if(B == 0 ){
return A;
}
return gcd2(B,A % B);
}

}``````
Copy The Code &

Input

cmd
2
2 6
10 11

Output

cmd
2
1

### #3 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<stdio.h>
#include<string.h>
char b[252];
int gcd(int a, int b){
if(!a) return b;
return gcd(b%a,a);
}
int main(){
int t,a,mod,i,l;
for(scanf("%d",&t);t--;){
mod = 0;
scanf("%d",&a);
scanf("%s",b);
if(!a){
printf("%s\n",b);
continue;
}
l = strlen(b);
for(i=0;i<l;i++){
mod = (mod*10 + b[i] - '0')%a;
}
printf("%d\n",gcd(mod,a));
}
return 0;
}``````
Copy The Code &

Input

cmd
2
2 6
10 11

Output

cmd
2
1