说明

给出两个正整数X和Y，求X和Y的最大公约数，奶牛可以轻松解决这个问题。农夫FarmerJohn决定改一改题目去考验奶牛。农夫决定询问奶牛Q个问题，每个问题的 格式是这样的：

农夫给定两个正整数a和b，农夫保证a<=b，然后农夫询问奶牛：在a至b的范围 内，有没有哪个整数既是X的约数同时又是Y的约数？如果有，输出最大的那个；如果没有，输出-1。

输入格式

第一行，两个正整数，X和Y。

第二行，一个整数数，Q。

接下来有Q行，每行两个正整数：a和b，其中保证a<=b。

输出格式

共Q行，每行一个整数，每行对应农夫的一个问题。

样例

200	120
3
9	40
25	35
10	15

40
-1
10

样例

10	10
2
1	6
5	5

5
5

提示

【数据规模】

1、对于40%的数据，1<=X<=100，1<=Y<=100，1<=Q<=100，1<=a<b<=100

2、对于100%的数据，1<=X<=1000000000，1<=Y<=1000000000，1<=Q<=30000，1<=a<b<=1000000000。

样例1解释

第一个问题：在 9 至 40 的范围内，既是 200 的约数，同时又是 120 的约数，共有 3 个，分别是：10,20,40，在 3 个之中，40 最大，所以输出 40。

第二个问题：在 25 至 35 的范围内，找不到既是 200 的约数，同时又是 120 的约数，所以输出-1。

第三个问题：在 10 至 15 的范围内，既是 200 的约数，同时又是 120 的约数，只有 10，所以输出 10。

样例2解释

第一个问题：在 1 至 6 的范围内，既是 10 的约数，同时又是 10 的约数，有 2 和 5，所以输出 5。

第二个问题：在 5 至 5 的范围内，既是 10 的约数，同时又是 10 的约数，只有 5，所以输出 5。