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: interview

Starter code:

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

# cook your dish here
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])


# cook your dish here
import math
t=int(input())
for i in range(t):
 a,b=map(int,input().split())
 print(math.gcd(a,b))

def compute_hcf(x, y):

# choose the smaller number
 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))

# cook your dish here
from math import gcd
mod = 10**9+7
for _ in range(int(input())):
 a,b = list(map(int,input().split()))
 # c = pow(a,b-2,b)
 # print(gcd(a,c))
 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)) 


# cook your dish here
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) 

# cook your dish here
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=[]
 #l.append(list(map(int,input().split(" "))))
 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)

 
 
 


# cook your dish here
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

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


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)

# cook your dish here
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))

# cook your dish here
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)

# cook your dish here
import sys
import numpy as np
#data = sys.stdin.readline()
#first = True
#a, b = [], []
for line in sys.stdin.readlines():
 #if first:
 T = int(line.replace("\n", ""))
 #first = False
 #continue
 break
 
 #l = line.replace("\n", "").split(' ') 
 #a.append(int(l[0]))
 #b.append(int(l[1]))
 
#a, b = np.array(a), np.array(b)

for i in range(T):
 print(1)