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

Solution:
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
    static long mod=((long)1e9)+7;//toString
    public static int gcd(int a,int b){if(b==0)return a;else return gcd(b,a%b);}
    public static long pow_mod(long x,long y){long res=1;x=x%mod;while(y > 0){if((y & 1)==1)res=(res * x)%mod;y=y>>1;x =(x * x)%mod;}return res;}
    public static int lower_bound(int[]arr,int val){int lo=0;int hi=arr.length-1;while(lo<hi){int mid=lo+((hi-lo+1)/2);if(arr[mid]==val){return mid;}else if(arr[mid]>val){hi=mid-1;}else lo=mid;}if(arr[lo]<=val)return lo;else return -1;}
    public static int upper_bound(int[]arr,int val){int lo=0;int hi=arr.length-1;while(lo<hi){int mid=lo+((hi-lo)/2);if(arr[mid]==val){return mid;}else if(arr[mid]>val){hi=mid;;}else lo=mid+1;}if(arr[lo]>=val)return lo;else return -1;}
    
    public static void main (String[] args) throws java.lang.Exception
    {
        Reader sn = new Reader();
        Print p = new Print();
        int a = sn.nextInt();
        int b = sn.nextInt();
        int gcd = gcd(a , b);
        TreeSet<Integer> divisors = new TreeSet<Integer>();
        for(int i = 1; (i * i) <= gcd; ++i){
            if((gcd % i) == 0){
                if(i == (gcd / i)){
                    divisors.add(i);
                }
                else{
                    divisors.add(i);
                    divisors.add(gcd / i);
                }
            }
        }
        int q = sn.nextInt();
        while(q-- > 0){
            int lo = sn.nextInt();
            int hi = sn.nextInt();
            int ans = divisors.floor(hi);
            if(ans >= lo){
                p.printLine(Integer.toString(ans));
            }
            else{
                p.printLine("-1");
            }
        }
        p.close();
    }
}
class Pair implements Comparable<Pair> {
		int val;
		int in;
		Pair(int a, int b){
			val=a;
	        in=b;
		}
		@Override
		public int compareTo(Pair o) {
			if(val==o.val)
			return Integer.compare(in,o.in);
			else
			return Integer.compare(val,o.val);
		}}
class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; }
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
        
        public String readWord()throws IOException
        {
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		}while (!isSpaceChar(c));
		return res.toString();
	    } 
	
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
class Print
{
    private final BufferedWriter bw;
    public Print()
    {
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public void print(String str)throws IOException
    {
        bw.append(str);
    }
    public void printLine(String str)throws IOException
    {
        print(str);
        bw.append("\n");
    }
    public void close()throws IOException
    {
        bw.close();
    }}