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:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(10**4)
from math import ceil,factorial,floor,gcd,log2,log10,sqrt
from collections import defaultdict as dd,Counter as cc,deque
from itertools import permutations as perm, combinations as comb
from heapq import heapify,heappush,heappushpop,nlargest,nsmallest
from bisect import bisect_left,bisect_right,bisect as bs

inpl=lambda : list(map(int,input().split()))
lstinp=lambda : list(input().split())
inpm=lambda : map(int,input().split())
inps=lambda :int(input())
inp=lambda : input()

def Divisors(n) : 
	l=[]
	i = 2
	while i <= sqrt(n): 
		if (n % i == 0) : 
			if (n // i == i) : 
				l.append(i)
			else : 
				l.append(i)
				l.append(n//i)
		i = i + 1
	return l

def SieveOfEratosthenes(n): 
	l=[]
	prime = [True for i in range(n+1)] 
	p = 2
	while (p * p <= n): 
		if (prime[p] == True): 
			for i in range(p * p, n+1, p): 
				prime[i] = False
		p += 1
	
	for p in range(2, n+1): 
		if prime[p]: 
			l.append(p)
	return l		

def primeFactors(n): 
	l=[]
	while n % 2 == 0: 
		l.append(2) 
		n = n / 2
		
	for i in range(3,int(sqrt(n))+1,2): 
		while n % i== 0: 
			l.append(i) 
			n = n / i 		
	if n > 2: 
		l.append(n)
	return(l)	
		

def Factors(n) : 
	result = []
	for i in range(2,(int)(sqrt(n))+1) : 
		if (n % i == 0) : 
			if (i == (n/i)) : 
				result.append(i)
			else : 
			    result.append(i)
			    result.append(n//i)
		
	result.append(1)
	result.append(n)
	return result

def maxSubArraySum(a): 
	
	max_so_far = 0
	max_ending_here = 0
	size=len(a)
	
	for i in range(0, size): 
		max_ending_here = max_ending_here + a[i] 
		if (max_so_far < max_ending_here): 
			max_so_far = max_ending_here 

		if max_ending_here < 0: 
			max_ending_here = 0
	return max_so_far

def longestsubarray(arr, n, k): 
    current_count = 0  
    # this will contain length of  
    # longest subarray found 
    max_count = 0
  
    for i in range(0, n, 1): 
        if (arr[i] % k != 0): 
            current_count += 1
        else: 
            current_count = 0
        max_count = max(current_count,max_count) 
      
    return max_count

def main():
    a,b=inpm()
    gg=gcd(a,b)
    fact=sorted(Factors(gg))
    q=inps()
    for _ in range(q):
        l,r=inpm()
        if l>gg:
            print(-1)
            continue
        if r>gg:
            r=gg

        x=fact[bisect_right(fact,r)-1]
        if x in range(l,r+1):
            print(x)
        else:
            print(-1) 


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()