Euclidean Algorithm — GCD

Practice this coding question on Coding Gurukul.

Problem statement

For each pair of nonnegative integers a and b, print their greatest common divisor (GCD) using the Euclidean algorithm. Repeatedly replace (a, b) with (b, a mod b) until b is 0. The remaining a is the answer. For this problem, gcd(0,0)=0. If exactly one value is 0, the answer is the other value. Use signed 64-bit integers. Worked example gcd(48,18)=6, gcd(0,7)=7, and gcd(13,17)=1.

Input format

First line: q. Next q lines: a b.

Output format

Print one greatest common divisor per line.

Constraints

1 <= q <= 100000; 0 <= a,b <= 10^18.

Sample input

3
48 18
0 7
13 17

Sample output

6
7
1

Sign in to run or submit a solution in C++, Java or Python.