Part 14 of 28 in Maths - Beginner set 01  

Greatest common divisor (GCD) by animeshn

Problem statement

Given two positive integers, find their greatest common divisor.

Input

First line of input will contain an integer T = number of test cases . Next T lines will each contain two numbers A and B separated by space. 1<= A,B <= 10^15

Output

For each test case, print on a single line the greatest common divisor of the two numbers.

Sample Input
5
2 4
11 17
35 14
55 15
12345 123
Sample Output
2
1
7
5
3
1) See input limit for A and B. 32 bit integer will overflow.
2) You need to think of an O(log n) algorithm. 
3) Have you heard of a mathematician named Euclid?


To try out your code



Sign in

Sign up