Martha đang phỏng vấn xin vào làm việc tại một công ty. Câu hỏi đầu tiên cô ấy phải giải quyết là: Cho một chiếc bánh mì hình chữ nhật kích thước ~ l ×b ~, hãy cắt bánh mì thành những miếng bánh hình vuông giống nhau có cạnh lớn nhất sao cho chiếc bánh ban đầu không có miếng thừa.

Dữ liệu vào

Gồm nhiều bộ dữ liệu:

• Dòng đầu ghi số nguyên ~ t ~ ~ (1 ≤ t ≤ 1000) ~ cho biết số lượng bộ dữ liệu
• ~ t ~ dòng tiếp theo mỗi dòng ghi hai số nguyên ~ l ~ và ~ b ~ cho biết kích thước của một chiếc bánh mì ~ ( 1 ≤ l, b ≤ 1000) ~.

Kết quả

• Với mỗi bộ dữ liệu tương ứng trong input đưa ra số lượng miếng bánh cắt được thỏa mãn yêu cầu bài toán.

Ví dụ:

Input 1

2
2 2
6 9 

Output 1

1
6