Problem: Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers.

A common divisor for two positive numbers is a number which both numbers are divisible by.

But your teacher wants to give you a harder task, in this task you have to find the greatest common divisor d between two integers a and b that is in a given range from low to high (inclusive), i.e. low ≤ d ≤ high. It is possible that there is no common divisor in the given range.

You will be given the two integers a and b, then n queries. Each query is a range from low to high and you have to answer each query.

Input

The first line contains two integers a and b, the two integers as described above (1 ≤ a, b ≤ 109). The second line contains one integer n, the number of queries (1 ≤ n ≤ 104). Then n lines follow, each line contains one query consisting of two integers, low and high (1 ≤ low ≤ high ≤ 109).

Output

Print n lines. The i-th of them should contain the result of the i-th query in the input. If there is no common divisor in the given range for any query, you should print -1 as a result for this query.

Examples

Input

9 27
3
1 5
10 11
9 11


Output

3
-1
9

Solution (in PYTHON):

Solution:
I=lambda:map(int,raw_input().split())
a,b=I()

def P(n):
    p=[0]*n
    f=[]
    for i in range(2,n):
        if not p[i]:
            f+=[i]
            k = i
            while k+i < n:
                k+=i
                p[k] = 1
    return f

def F(n):
    s=int(n**0.5)+1
    p=P(s)
    if n==1: return [1]
    r=[]
    for c in p:
        if c * c > n:
            break
        while n%c == 0:
            r+=[c]
            n /= c
    if n > 1:r+=[n]
    return r


def div(i,r,g):
    if i == len(g):
        return set([r])
    return div(i+1,r,g)|div(i+1,r*g[i],g)

def D(n):
    d=F(n)
    return div(0,1,d)
            
n,=I()
l=sorted(list(D(a)&D(b)))
from bisect import *
#print l
for i in range(n):
    a,b=I()
    B=bisect_right(l, b)-1
    A=bisect_left(l,a)
#    print A,B
    print -1 if B <A or B==len(l) else l[B]