Thầy giáo định nghĩa ước chung lớn nhất ~d~ của hai số nguyên dương ~a~ và ~b~ nằm trong đoạn ~[l, r]~ là ước số ~d~ lớn nhất trong các ước của hai số ~a, b~ và ~l \le d \le r~.

Mai được thầy giáo cho hai số nguyên dương ~a, b~ và ~n~ truy vấn. Mỗi truy vấn là một đoạn ~[l, r]~ và Mai phải tìm ra ước chung lớn nhất của 2 số ~a, b~ trong từng đoạn ~[l, r]~ đó. Bạn hãy lập trình giúp Mai giải quyết bài toán trên.

Dữ liệu

Vào từ tệp văn bản CAL.INP:

• Dòng đầu tiên chứa hai số nguyên ~a~ và ~b~ (~1 \le a, b \le 10^9~);
• Dòng thứ hai chứa một số nguyên duy nhất ~n~ là số truy vấn (~1 \le n \le 10^5~);
• ~n~ dòng tiếp theo: mỗi dòng chứa một truy vấn gồm hai số nguyên ~l~ và ~r~ (~1 \le l \le r \le 10^9~).

Kết quả

Đưa ra tệp văn bản CAL.OUT ~n~ dòng. Dòng thứ ~i~ sẽ là kết quả tìm được của truy vấn thứ ~i~ theo dữ liệu vào. Nếu như không tìm được ước chung lớn nhất nào, in ra ~-1~.

Ví dụ

CAL.INP

9 27
3
1 5
10 11
3 11

CAL.OUT

3
-1
9

Giải thích:

• Ở truy vấn thứ nhất, ước chung của hai số 9 và 27 trong đoạn ~[1, 5]~ có 2 ước số 1 và 3. Do đó ước chung lớn nhất trong đoạn này sẽ là 3;
• Ở truy vấn thứ ba, ước chung của hai số 9 và 27 trong đoạn ~[3, 11]~ có hai số là 3 và 9. Do đó ước chung lớn nhất sẽ là 9.

Giới hạn

• Có 40% số test ứng với 40% số điểm của bài có ~1 \le n \le 10^2~, ~1 \le l \le r \le 10^3~;
• Có 30% số test ứng với 30% số điểm của bài có ~1 \le n \le 10^4~;
• Có 30% số test ứng với 30% số điểm của bài có ~1 \le n \le 10^5~.