# Problem Definition

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 ( and ).

**Output**

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

**More on this problem is available here.**

# Solution

*Greatest common divisor* is the largest number that divides both number without any reminder. Thus, GCD is also called *Highest Common Divisor *(HCF), or *Greatest Common Factor *(GCF).

The main trick used in the solution lies in the `mod'`

function, which effectively reduces the range of the numbers to , that is:

where is the outcome of `mod'`

function .

Afterwards, a normal `gcd`

function can simply be applied on to compute the result.