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 PYTHON3):

Solution:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import math
def binarySearchLeft(arr,l,r,x):
    temp=False
    while l<=r:
        mid=(l+r)//2
        if arr[mid]==x:
            return mid
        elif arr[mid]<x:
            temp=True
            ans=mid
            l=mid+1
        else:
            r=mid-1
    if temp:
        return ans+1
    return -2
def binarySearchRight(arr,l,r,x):
    temp=False
    while l<=r:
        mid=(l+r)//2
        if arr[mid]==x:
            return mid
        elif arr[mid]>x:
            temp=True
            ans=mid
            r=mid-1
        else:
            l=mid+1
    if temp:
        return ans-1
    return -2
def factors(n):
    lis=[1,n]
    i=2
    a=math.sqrt(n)
    while i<=a:
        if n%i==0:
            if i==a:
                lis.append(i)
            else:
                lis.append(i)
                lis.append(n//i)
        i+=1
    return lis
a,b=list(map(int,input().split()))
arr1=factors(a)
arr2=factors(b)
arr1.sort()
arr2.sort()
lis=[]
j=0
x=len(arr1)
y=len(arr2)
for i in range(x):
    while j<y and arr2[j]<=arr1[i]:
        if arr2[j]==arr1[i]:
            lis.append(arr2[j])
        j+=1
len1=len(lis)
n=int(input())
for i in range(n):
    l,r=list(map(int,input().split()))
    ind1=binarySearchLeft(lis,0,len1-1,l)
    ind2=binarySearchRight(lis,0,len1-1,r)
    if (ind1>=len1 and ind2==-2) or (ind1==-2 and ind2<=-1):
        print(-1)
    elif ind1<len1 and ind1>-1 and ind2<len1 and ind2>-1 and lis[ind1]>lis[ind2]:
        print(-1)
    else:
        if ind2==-2:
            print(lis[-1])
        else:
            print(lis[ind2])