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:
import sys
import math
from Queue import Queue
from sets import Set

class pythonin:
    _data = []
    _ldata = []
    _cur = 0
    _lcur = 0
    
    def __init__(self):
        while True:
            try: self._ldata.append(raw_input())
            except EOFError : break

    def _convert(self):
        if self._lcur == len(self._ldata) : return
        l = self._ldata[self._lcur].split(" ")
        self._lcur += 1
        for x in l :
            if x != "" and x != "\t" :
                self._data.append(x)
        
    def eof(self) : 
        self._convert()
        return self._cur == len(self._data)

    def nextToken(self) :
        if self.eof() : return
        self._cur += 1
        return self._data[self._cur - 1]
    
    def nextInt(self) :
        return int(self.nextToken())
    
    def nextFloat(self) :
        return float(self.nextToken())
    
    def nextLine(self) :
        if self._lcur == len(self._ldata) : return 
        self._lcur += 1
        return self._ldata[self._lcur - 1]
    
#sys.stdin = open("input.txt", "r")
#sys.stdout = open("output.txt", "w")

pin = pythonin()

a = pin.nextInt()
b = pin.nextInt()

div = []

mx = int(math.sqrt(max(a, b) + 1)) + 1

for i in xrange(1, mx) :
    if a % i == 0 or b % i == 0:
        if a % i == 0 and b % i == 0 : div.append(i)
        ra = a / i
        rb = b / i
        if a % ra == 0 and b % ra == 0 :
            div.append(ra)
        if a % rb == 0 and b % rb == 0 :
            div.append(rb)

div = list(set(div))
div.sort()
 
n = pin.nextInt()

for i in xrange(0, n):
    
    low = pin.nextInt()
    high = pin.nextInt()
    
    l = 0
    r = len(div)
    
    while r - l > 1 :
        t = (l + r) / 2
        if high < div[t] : r = t
        else :             l = t
    
    if  low <= div[l] <= high : print div[l]
    else :                      print -1



#print ("Press any key to continue")
#raw_input()