#193. RESTAURANT - Nhà hàng bánh ngọt

HD được nhận vào làm đầu bếp tại một nhà hàng bánh ngọt nổi tiếng. Nhiệm vụ đầu tiên của HD là phải cắt một chiếc bánh hình chữ nhật kích thước thỏa:

• Các miếng bánh cắt thành các hình vuông có kích thước bằng nhau;
• Độ dài cạnh hình vuông là lớn nhất.

Yêu cầu: Bạn hãy trả lời câu hỏi dạng có thể cắt được bao nhiêu miếng bánh hình vuông có cạnh lớn nhất?

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương là số lượng câu hỏi;
• dòng tiếp theo, dòng thứ là câu hỏi có số nguyên dương .

Dữ liệu ra:

• Ghi ra trên dòng, dòng thứ là đáp án câu hỏi .

Ví dụ:

Dữ liệu vào:

2
2 2
6 9

Dữ liệu ra:

1
6

Giải thích:

• Câu hỏi : bánh hình vuông cỡ lớn nhất có bánh;
• Câu hỏi : Từ bánh ta cắt thành có thể cắt thành:
  • bánh ;
  • bánh .

Đáp án: .