Cho hai số \(a\) và \(b\). Tìm ước chung lớn nhất của hai số.

Input

• Dòng đầu tiên chứa số nguyên \(t(t \leq 10^5)\) là số lượng cặp số cần tìm ước chung lớn nhất.
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) \(b(1 \leq a,b \leq 10^9)\).

Output

• Với mỗi cặp số, in ước chung lớn nhất của cặp số đó.

2
2 3 
10 15

1
5