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 sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
# sys.setrecursionlimit(int(pow(10,6)))
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.stdin = open("input.txt", "r")
except:
    pass


# @lru_cache(None)
a,b=L()
sa=set()
sb=set()
sa.add(a)
sb.add(b)
for i in range(2,int(a**0.5)+2):
    if a%i==0:
        sa.add(i)
        sa.add(a//i)
for i in range(2,int(b**0.5)+2):
    if b%i==0:
        sb.add(i)
        sb.add(b//i)
s=sa.intersection(sb)
s.add(1)
s=sorted(list(s))
# print(s)
q=L()[0]
n=len(s)
for i in range(q):
    a,b=L()
    l=bl(s,a)
    r=br(s,b)
    # print(l,r)
    if l>r:
        print(-1)
        continue
    if l==r:
        if l<len(s) and l>=0 and s[l]>=a and s[l]<=b:
            print(s[l])
        else:
            print(-1)
        continue
    while(r>n):
        r-=1
    if l<=r:
        print(s[r-1])
    else:
        print(-1)