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.*;


 
public class Main {

    int n;
    int[] seg;
    HashMap<Integer, Integer> pos = new HashMap<>();

    public void update(int idx, int val){
        idx += n;
        seg[idx] = val;
        idx /= 2;

        while(idx > 1){
            seg[idx] = Math.max(seg[idx * 2], seg[idx * 2 + 1]);
            idx /= 2; 
        }
    }

    public int query(int l, int r){

        l += n;
        r += n;
        int res = 0;

        while(l < r){
            if(l % 2 == 1){
                res = Math.max(res, seg[l]);
                l++;
            }
            if(r % 2 == 1){
                r--;
                res = Math.max(res, seg[r]);
            }
            l /= 2;
            r /= 2;
        }

        return res;

    }


    public void solve() throws IOException{

        long a = in.nextLong();
        long b = in.nextLong();
        n = in.nextInt();

        List<Long> divisors = new ArrayList<>();
        long gcd = gcd(a, b);

        for(long i = 1; i * i <= gcd; i++){
            if(gcd % i == 0){
                divisors.add(i);
                divisors.add(gcd / i);
            }
        }

        Collections.sort(divisors);

        for(int i = 0; i < n; i++){
            long l = in.nextLong();
            long r = in.nextLong();
            long max = -1;
            for(long val: divisors){

                if(val >= l && val <= r){
                    max = Math.max(max, val);
                }

            }
            out.println(max);

        }
        
        return;
    }





    public BigInteger gcdBigInt(BigInteger a, BigInteger b){

        if(a.compareTo(BigInteger.valueOf(0L)) == 0){
            return b;
        }else{
            return gcdBigInt(b.mod(a), a);
        }

    }

 
    FastScanner in;
    PrintWriter out;
 
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public boolean isPrime(long num){

        if(num == 0 || num == 1){
            return false;
        }

        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }

    public class Pair<A, B>{
        public A x; 
        public B y;

        Pair(A x, B y){
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!x.equals(pair.x)) return false;
            return y.equals(pair.y);
        }

        @Override
        public int hashCode() {
            int result = x.hashCode();
            result = 31 * result + y.hashCode();
            return result;
        }

    }

    class Tuple{
        int x; int y; int z;
        Tuple(int ix, int iy, int iz){
            x = ix;
            y = iy;
            z = iz;
        }
    }
}