#1087 최대 공약수 구하기 2

323  3 s   128 MB  

Description

최대공약수란, $0$이 아닌 두 정수의 공통되는 약수 중에서 가장 큰 수를 말한다.

두 정수 $a$와 $b$의 최대공약수는 $gcd(a, b)$로 표기하거나, $(a, b)$로도 표기한다.

 

Input

입력의 첫 줄에는 Test Case의 수 $T$가 입력된다.

각 Test Case에 대해 $a, b$ 가 빈 칸을 구분으로 한 줄에 입력된다.$(1 \leq a, b \leq 10^{9})$

 

Output

각 Test Case에 대해 $gcd(a, b)$를 출력한다.

 

 

 

Sample Input

Sample Output

3
12 18
12510 15124
1495434245 1156765861
6
2
1