bhola-needs-help

Chotu is having his mathematics test tomorrow. Chotu was solving a problem and found out that it is quite difficult for him. Given two integers A and B and some Q queries. Each query contains two numbers L and R such that L ≤ R. Find greatest number D such that L ≤ D and D ≤ R such that A and B both are divisible by D. If there is no such number answer is -1. Chotu asks your help to solve this problem as he wants to practice each and every question.

Input

The first line contains two integers A and B, the two integers as described above. 
The second line contains one integer Q, the number of queries. 
 Then Q lines follow, each line contains one query consisting of two integers, L and R.
Constraints

1 ≤ A, B ≤ 10^14
1 ≤ Q ≤ 10^6
1 ≤ L ≤ R ≤ 10^18

SAMPLE INPUT
9 27
3
1 5
6 7
8 15

SAMPLE OUTPUT
3
-1
9

Source: hackerearth | Difficulty: EASY


Solutions: