Euclidean Algorithm -- Problem E (5 points)


The Euclidean algorithm for finding the largest number which will divide evenly into two numbers (the GCD) is as follows:

Suppose the numbers are a and b, and a > b. Divide a by b. If there is no remainder then b is the solution. If there is a remainder, call it c; note b > c. Then rename b as a, c as b and repeat this process until the remainder is zero. The final value of b is the GCD.

     Example 66 and 27

     66 divided by 27 gives remainder 12
     27 divided by 12 gives remainder 3
     12 divided by 3 gives remainder 0
     Thus the GCD is 3
    

The input file for this problem is called PROBLEME.DAT and consists of lines, each containing a pair of numbers, which will be positive integers up to 1,000,000,000. The file will be terminated by a line containing a pair of zeroes.

Output, which must be written to standard output (the screen), must be the GCD for each pair of input numbers, leftjustified on its line.

Example Input

65 27
999 1269
0 0

Example Output

1
27