Ciri has recently learnt how to calculate GCD (greatest common divisor) of two numbers. To test her understanding, Geralt asks her to calculate GCD of 2 numbers a and b. Ciri easily calculates the answer. Now to make the problem harder, he has asked q questions in which each one requires to calcuate greatest number in range [l,r] which divides both a and b. Ciri won't be able to solve all questions in time. So, she has asked you to solve the questions for her.
Input Format--
First line consists of three integers, a, b and q.
Each of next q lines consists of two integers l and r, denoting the given range.
Output Format--
Output q lines giving answer to each of the corresponding range.
If there is no valid number in given range, output "-1"(without quotes).
Constraints--
1≤a,b≤109
1≤q≤106
1≤l≤r≤109
For first question, 4 is the largest number in range [1, 20] which divides both 12 and 16.
For second question, 4 is the largest number in range [1, 4] which divides both 12 and 16.
For third question, 2 is the largest number in range [1, 3] which divides both 12 and 16.
For fourth question, there is no number in range [10, 20] which divides both 12 and 16.
For second question, there is no number in range [10, 30] which divides both 12 and 16.
