Quân hiện tại đang có hai hộp kẹo có số kẹo lần lượt là \(a\) và \(b\). Quân là một người thích cho đi nhưng lại là người bị mắc chứng OCD, nên quân muốn tìm một số \(x\) sao cho khi lấy đi \(x\) lần với mỗi hộp kẹo (với mỗi lần lấy kẹo là một số chia hết cho số kẹo ban đầu hộp kẹo đó), cả hai hộp kẹo đó đều sẽ hết.

Giả sử Quân đang có số kẹo trong 2 hộp kẹo lần lượt là 4 và 6, nên ta tìm được \(x = 2\) (với số kẹo bị lấy đi mỗi lần của 2 hộp lần lượt là 2 và 3).

Hãy giúp Quân tìm ra số \(x\) lớn nhất có thể.

INPUT FORMAT

Dòng đầu tiên gồm \(q\) truy vấn \((1 \leq q \leq 20)\).

\(q\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương \(a, b\) cách nhau bởi một dấu cách \((1 \leq a, b \leq 10^5)\).

OUTPUT FORMAT

In ra \(q\) dòng, mỗi dòng chứa 1 số nguyên dương duy nhất là số \(x\).

Ví dụ:

Input

2
4 6
4 8

Ouput

2
4

Giải thích ví dụ mẫu:

Ví dụ 1:

• Để tìm số kẹo lớn nhất x sao cho x có thể chia hết cho cả số kẹo trong hai hộp 4 và 6, ta tính ước chung lớn nhất (GCD) của 4 và 6, kết quả là 2.

Ví dụ 2:

• Để tìm số kẹo lớn nhất x sao cho x có thể chia hết cho cả số kẹo trong hai hộp 4 và 8, ta tính GCD của 4 và 8, kết quả là 4.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House