Xếp Cặp Kênh Bắt Bộ Âm Thanh

Mô tả

Kỹ sư âm thanh của nhà hát Quân Đoàn đang chuẩn bị hệ thống loa cho đêm diễn nghệ thuật. Có một bộ thu âm kỹ thuật số gắn sẵn n kênh, mỗi kênh hoạt động theo một chu kỳ lấy mẫu riêng (đơn vị mili giây). Khi hai kênh chạy chung một chu kỳ, sóng âm của chúng sẽ khớp nhịp và tạo ra hiệu ứng cộng hưởng tốt nhất.

Để bắt bộ các kênh vào một thẻ xử lý chung, kỹ sư cần kiểm tra từng cặp kênh trong danh sách truy vấn: cặp nào có cùng một chu kỳ quét nền lớn nhất (tức là ước chung lớn nhất của hai chu kỳ lấy mẫu khác 1) thì sẽ được xếp chung thẻ. Nhiệm vụ của bạn là cho mỗi cặp truy vấn, hãy tính ước chung lớn nhất của hai chu kỳ.

Đầu vào

• Dòng đầu tiên chứa số nguyên q — số lượng truy vấn (1 ≤ q ≤ 1000).
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên a và b — chu kỳ lấy mẫu của hai kênh cần kiểm tra (1 ≤ a, b ≤ 10⁹).

Đầu ra

• Với mỗi truy vấn, in ra trên một dòng số nguyên là ước chung lớn nhất của a và b.

Ràng buộc

• 1 ≤ q ≤ 1000.
• 1 ≤ a, b ≤ 10⁹.
• Tổng số lượng truy vấn nhỏ, máy chấm cho phép giải từng truy vấn trong O(log(min(a, b))).

Ví dụ

Đầu vào:

3 12 18 17 5 100 100

Đầu ra:

6 1 100

Giải thích từng bước:

• Truy vấn 1: 12 và 18. Ước của 12 là 1, 2, 3, 4, 6, 12. Ước của 18 là 1, 2, 3, 6, 9, 18. Ước chung lớn nhất là 6.