给出两个正整数 X 和 Y，求 X 和 Y 的最大公约数，奶牛可以轻松解决这个问题。 农夫 Farmer John 决定改一改题目去考验奶牛。农夫决定询问奶牛 Q 个问题，每个问题的 格式是这样的： 农夫给定两个正整数 a 和 b，农夫保证 a < = b，然后农夫询问奶牛：在 a 至 b 的范围 内，有没有哪个整数既是 X 的约数同时又是 Y 的约数？如果有，输出最大的那个；如果没 有，输出-1。

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

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

第一个问题：在 9 至 40 的范围内，既是 200 的约数， 同时又是 120 的约数，共有 3 个，分别是：10,20,40， 在 3 个之中，40 最大，所以输出 40。 第二个问题：在 25 至 35 的范围内，找不到既是 200 的 约数，同时又是 120 的约数，所以输出-1。 第三个问题：在 10 至 15 的范围内，既是 200 的约数， 同时又是 120 的约数，只有 10，所以输出 10。


样例输入
10 10 
2 
1 6 
5 5


样例输出
5 
5


第一个问题：在 1 至 6 的范围内，既是 10 的约数，同 时又是 10 的约数，有 2 和 5，所以输出 5。 第二个问题：在 5 至 5 的范围内，既是 10 的约数，同 时又是 10 的约数，只有 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。

2016年区赛