Chotu Needs Help

0

0 votes
Easy-Medium
Problem

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

Sample Input
9 27
3
1 5
6 7
8 15
Sample Output
3
-1
9
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?