You are given two integers a and b.There are queries containing two integers l and r.Now, you have to find the greatest common divisor of a and b lying in the range l to r(inclusive).It may happen that there exists no such divisors so,in such cases output -1.

Input

First line of input contains two positive integers a and b.(1<=a,b<=10^9).
Second line contains q(1<=q<=10^4),the number of queries.
Next q lines contain value of l and r respectively.(1<=l,r<=10^9).

Output

Output contains q lines containing answer for each query.