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
# 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))

# 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))
