Rushitote went to a programming contest to distribute apples and oranges to the contestants.   
He has N apples and M oranges, which need to be divided equally amongst the contestants. Find the maximum possible number of contestants such that:
Every contestant gets an equal number of apples; and
Every contestant gets an equal number of oranges.

Note that every fruit with Rushitote *must* be distributed, there cannot be any left over.

For example, 2 apples and 4 oranges can be distributed equally to two contestants, where each one receives 1 apple and 2 oranges.  
However, 2 apples and 5 oranges can only be distributed equally to one contestant.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two space-separated integers N and M — the number of apples and oranges, respectively.

------ Output Format ------ 

For each test case, output on a new line the answer: the maximum number of contestants such that everyone receives an equal number of apples and an equal number of oranges.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N , M ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1 5
2 4
4 6
----- Sample Output 1 ------ 
1
2
2
----- explanation 1 ------ 
Test case $1$: There's only one apple, so distributing to more than one person is impossible.

Test case $2$: As explained in the statement, $2$ people can each receive $1$ apple and $2$ oranges.

Test case $3$: $2$ people can each receive $2$ apples and $3$ oranges. It's not possible to distribute equally to more than two people.

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(gcd(n, m))


import math
n = int(input())
for i in range(1, n + 1):
	(a, b) = map(int, input().split())
	c = math.gcd(a, b)
	print(c)


n = int(input())
for i in range(1, n + 1):
	(a, b) = map(int, input().split())
	while b:
		(a, b) = (b, a % b)
	print(a)


for _ in range(int(input())):
	l = sorted(list(map(int, input().split())))
	while True:
		if l[1] % l[0] == 0:
			print(l[0])
			break
		else:
			l[0] = min(l[0], l[1] - l[0])
			l[1] = max(l[0], l[1] - l[0])


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = math.gcd(n, m)
	print(ans)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(math.gcd(a, b))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	while m:
		(n, m) = (m, n % m)
	print(n)


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	m = max(a, b)
	if a == 1 or a == 2:
		print(a)
	else:
		print(gcd(a, b))


import math
t = int(input())
for i in range(t):
	(a, o) = map(int, input().split())
	print(math.gcd(a, o))


import math
for i in range(int(input())):
	(x, y) = map(int, input().split())
	if y == 0:
		print(x)
	else:
		print(math.gcd(y, x))


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
for i in range(int(input())):
	(x, y) = map(int, input().split())
	a = gcd(x, y)
	print(a)


import math
for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(math.gcd(a, b))


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 1 or b == 1:
		print(min(a, b))
	else:
		print(math.gcd(a, b))


def gcd(a, b):
	if b == 0:
		return a
	elif a == b:
		return b
	else:
		return gcd(b, a % b)
for i in range(0, int(input())):
	l = list(map(int, input().split()))
	N = l[0]
	M = l[1]
	rm = gcd(max(N, M), min(M, N))
	print(rm)


import math
t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	print(math.gcd(n, m))
	t = t - 1


import math
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	gcd = math.gcd(n, m)
	if gcd == 1:
		print(1)
	else:
		print(gcd)


import math as t
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = t.gcd(n, m)
	print(a)


p = int(input())
for i in range(p):
	(x, y) = map(int, input().split())
	while y:
		(x, y) = (y, x % y)
	print(x)


import math
n = int(input())
for i in range(0, n):
	(a, b) = map(int, input().split())
	ans = math.gcd(b, a)
	print(ans)


import math
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	z = math.gcd(m, n)
	print(z)


import math
for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(math.gcd(x, y))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	while m:
		(n, m) = (m, n % m)
	print(n)


import math
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	k = math.gcd(a, b)
	print(k)


import math
n = int(input())
for i in range(n):
	l = [int(x) for x in input().split()]
	a = l[0]
	b = l[1]
	ans = math.gcd(a, b)
	print(ans)


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	while n != m:
		if n > m:
			n -= m
		else:
			m -= n
	print(n)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().strip().split())
	print(math.gcd(n, m))


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	while m:
		(n, m) = (m, n % m)
	print(n)


import math
for test in range(int(input())):
	(n, m) = map(int, input().split())
	print(math.gcd(n, m))


t = int(input())
for i in range(t):
	(a, o) = map(int, input().split())
	while o:
		(a, o) = (o, a % o)
	print(a)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	ans = math.gcd(x, y)
	print(ans)


t = int(input())
for x in range(t):
	(a, b) = map(int, input().split())

	def gcd(a, b):
		if b == 0:
			return a
		else:
			return gcd(b, a % b)
	GCD = gcd(a, b)
	print(GCD)


import math
t = int(input())
for bunny in range(t):
	(n, m) = map(int, input().split())
	print(math.gcd(n, m))


import math

def gcd(m, n):
	return math.gcd(n, m)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(gcd(a, b))


def gcd(n, m):
	if n == 0:
		return m
	elif m == 0:
		return n
	else:
		return gcd(m, n % m)
for i in range(int(input())):
	(n, m) = map(int, input().split())
	k = gcd(n, m)
	print(k)


import math

def app_orng(n, m):
	return math.gcd(n, m)
T = int(input())
for j in range(T):
	(n, m) = map(int, input().split())
	print(app_orng(n, m))


def app_orng(n, m):
	r = n
	while r > 0:
		n = m
		m = r
		r = n % m
	return m
T = int(input())
for j in range(T):
	(n, m) = map(int, input().split())
	print(app_orng(n, m))


from math import gcd
t = int(input())
for i in range(t):
	(x, y) = list(map(int, input().split()))
	print(gcd(x, y))