Pushkar is very good in Number Theory. He takes two numbers $A\ and\ B$ and declares them a Pushkar Pair. Pushkar Pair has a property that $A$ has a $Modular\ Inverse$ modulo $B$.  
He asks you to tell him the largest number $L$ that divides both of them.  

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, two integers $A, B$. 

-----Output:-----
For each testcase, output in a single line the integer $L$.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq A,B \leq 10^4$

-----Sample Input:-----
1
3 4

-----Sample Output:-----
1

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

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


t = int(input())

def gcd(a, b):
	big = max(a, b)
	small = min(a, b)
	while small:
		(big, small) = (small, big % small)
	return big
for __ in range(t):
	(a, b) = list(map(int, input().split(' ')))
	print(gcd(a, b))


def hcfnaive(a, b):
	if b == 0:
		return a
	else:
		return hcfnaive(b, a % b)
for _ in range(int(input())):
	(num1, num2) = map(int, input().split(' '))
	print(hcfnaive(num1, num2))


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	lis = []
	if a >= b:
		for i in range(1, a + 1):
			if a % i == 0:
				if b % i == 0:
					lis.append(i)
	else:
		for i in range(1, b + 1):
			if b % i == 0:
				if a % i == 0:
					lis.append(i)
	print(lis[-1])


def compute_hcf(x, y):
	if x > y:
		smaller = y
	else:
		smaller = x
	for i in range(1, smaller + 1):
		if x % i == 0 and y % i == 0:
			hcf = i
	return hcf
for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(compute_hcf(x, y))


from math import gcd
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(gcd(a, b))


def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(computeGCD(a, b))


import math
T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	print('', end='')
	print(math.gcd(A, B))


def hcf(x, y):
	if y == 0:
		return x
	else:
		return hcf(y, x % y)
i = int(input())
for j in range(i):
	m = input()
	m = m.split()
	a = int(m[0])
	b = int(m[1])
	if a >= b:
		print(hcf(a, b))
	else:
		print(hcf(b, a))


for i in range(int(input())):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	if a > b:
		(a, b) = (b, a)
	r = 1
	for e in range(1, a + 1):
		if a % e == 0 and b % e == 0:
			r = e
	print(r)


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


def compute_hcf(x, y):
	if x > y:
		smaller = y
	else:
		smaller = x
	lst = []
	for i in range(1, smaller + 1):
		if x % i == 0 and y % i == 0:
			lst.append(i)
	return max(lst)
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	print(compute_hcf(a, b))


t = int(input())
for i in range(t):
	[a, b] = list(map(int, input().split()))
	gr = 0
	for j in range(1, max(a, b) + 1):
		if a % j == 0 and b % j == 0:
			gr = j
	print(gr)


def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		(a, b) = (b, a % b)
	return a
for a0 in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(gcd(a, b))


n = int(input())
l = []
ans = []
i = 1
for p in range(0, n):
	ll = []
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	ll.append(a)
	ll.append(b)
	l.append(ll)
for j in range(0, len(l)):
	if l[j][0] == 0:
		gcd = l[j][1]
	if l[j][1] == 0:
		gcd = l[j][0]
	if l[j][0] == l[j][1]:
		gcd = l[j][0]
	while i <= l[j][0] and i <= l[j][1]:
		if l[j][0] % i == 0 and l[j][1] % i == 0:
			gcd = i
		i = i + 1
	ans.append(gcd)
for k in ans:
	print(k)


t = int(input())
while t > 0:
	(m, n) = map(int, input().split())
	if m > n:
		for i in range(n, 0, -1):
			if m % i == 0 and n % i == 0:
				print(i)
				break
	else:
		for i in range(m, 0, -1):
			if m % i == 0 and n % i == 0:
				print(i)
				break
	t -= 1


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


def l(a, b):
	if b == 0:
		return a
	else:
		return l(b, a % b)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(l(a, b))


t = int(input())
while t > 0:
	t -= 1
	(a, b) = list(map(int, input().split()))
	ans = 1
	for i in range(2, a):
		if a % i == 0 and b % i == 0:
			ans = i
	print(ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 1
	for i in range(1, max(a, b)):
		if a % i == 0 and b % i == 0:
			if i > ans:
				ans = i
	print(ans)


import sys
import numpy as np
for line in sys.stdin.readlines():
	T = int(line.replace('\n', ''))
	break
for i in range(T):
	print(1)