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 <= 1014
1 <= Q <= 106
1 <= L <= R <= 1018