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.util.*;
import java.math.*;
import java.lang.*;

import static java.lang.Math.*;

public class ModifiedGCD implements Runnable {

    long mod = 1000000000 +7;
    InputReader read = new InputReader(System.in);
    /*
        less than return 1 => large number first;
    */

    ArrayList< Node > arr = new ArrayList<>();

    public void run() {
        int a = read.nextInt();
        int b = read.nextInt();
        int q = read.nextInt();
        int[][] values = new int[q][2];

        if(a>b){
            int temp = b;
            b = a;
            a = temp;
        }
        HashSet<Integer> map = new HashSet<>();

        for(int i=1;i*i<=a;i++){
            if(a%i == 0){
                if(b%i == 0){
                    if(!map.contains(i)){
                        arr.add(new Node(i,0,1));
                        map.add(i);
                    }
                }
                int temp = a/i;
                if(b%temp == 0){
                    if(!map.contains(temp)){
                        map.add(temp);
                        arr.add(new Node(temp,0,1));
                    }
                }
            }
        }

        for(int i=0;i<q;i++){
            int temp;
            temp = read.nextInt();
            values[i][0] = temp;
            if(!map.contains(temp)){
                arr.add(new Node(temp,0,0));
                map.add(temp);
            }
            temp = read.nextInt();
            values[i][1] = temp;
            if(!map.contains(temp)){
                arr.add(new Node(temp,0,0));
                map.add(temp);
            }
        }

        Collections.sort(arr,new NodeComp());

        int min = -1;

        for(int i=0;i<arr.size();i++){
            if(arr.get(i).type == 1) min = arr.get(i).num;
            arr.get(i).div = min;
        }

        for(int i=0;i<q;i++){
            int temp = binarySearch(values[i][1], 0, arr.size()-1);
            if(temp < values[i][0]) System.out.println(-1);
            else System.out.println(temp);
        }
    }

    int binarySearch(int value,int low,int high){
        int mid = (low+high)/2;

        if(arr.get(mid).num == value){
            return arr.get(mid).div;
        }else if( value < arr.get(mid).num){
            return binarySearch(value, low, mid-1);
        }else{
            return binarySearch(value, mid+1, high);
        }
    }

    class Node{
        int num;
        int div;
        int type;
        Node(int num,int div,int type){
            this.num = num;
            this.div = div;
            this.type = type;
        }
    }

    class NodeComp implements Comparator<Node>{
        @Override
        public int compare(Node a,Node b){
            if(a.num < b.num) return -1;
            else if(a.num > b.num) return 1;
            else return 1;
        }
    }

    long log2(long a){ return (long)(Math.log(a)/Math.log(2));}

    public long modAdd(long a, long b) { return (a % mod + b % mod) % mod;}

    public long modSub(long a, long b) { return ((a % mod - b % mod) % mod);}

    public long modMul(long a, long b) { return ((a % mod) * (b % mod)) % mod;}

    public long modDiv(long a, long b) { return ((a % mod) * (binaryExp(b, mod - 2))) % mod;}

    public long modPow(long a) { return a % (mod - 1);}

    public long binaryExp(long a, long pow) {
        a = a % mod;
        if (pow == 0) {
            return 1;
        } else if (pow == 1) {
            return a;
        } else {
            long half = pow / 2;
            long temp = binaryExp(a, half);
            if (pow % 2 == 0) {
                return (temp * temp) % mod;
            } else {
                return ((a % mod) * ((temp * temp) % mod)) % mod;
            }
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new ModifiedGCD(), "Main", 1 << 27).start();
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            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 boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}