PES16GCD - GCD of non-negative integers

no tags 

Find GCD (greatest common divisor) of two non-negative integers using Euclid’s algorithm.

Input

Input begins with t (1 ≤ t ≤ 100,000) of number of test-cases in the first line and the test-cases are in the following lines. Each test-case has m and n (1 ≤ m, n ≤ 1,000,000) on a single line separated by a space.

Output

For each test-case, print the GCD of m and n in a new line.

Example

Input:
5
60 24
100 101
120 420
0 123
123 0

Output:
12
1
60
123
123

hide comments
Prof. Channa Bankapur: 2016-01-25 04:12:58

Sorry for the restriction. This problem is a part of the tutorial problems of a course I'm instructing. The course restricts the algorithms to be implemented in C.

wisfaq: 2016-01-14 14:33:36

Is there any valid reason to restrict the solutions to C?


Added by:Prof. Channa Bankapur
Date:2016-01-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C