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 static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
    public static void main(String[] args) throws IOException {
        new Thread(null, new Runnable() {
            public void run() {
                try {
                    try {
                        if (new File("input.txt").exists())
                            System.setIn(new FileInputStream("input.txt"));
                    } catch (SecurityException e) {}
                    new Main().run();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }, "1", 1L << 24).start(); 
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");
    
    int A;
    int B;
    
    int[] divs = new int [100000];
    int dNum = 0;
    
    void run() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);

        A = nextInt();
        B = nextInt();        
        
        int gcd = gcd(A, B);
        
        for (int d = 1; d * d <= gcd; d++)
            if (gcd % d == 0) {
                divs[dNum++] = d;
                if (d * d != gcd)
                    divs[dNum++] = gcd / d;
            }
        divs = Arrays.copyOf(divs, dNum);
        sort(divs);
        
        // System.out.println(Arrays.toString(divs));
        
        lp: for (int Q = nextInt(); Q --> 0; ) {
            int low = nextInt();
            int high = nextInt();
            
            for (int j = dNum - 1; j >= 0; j--) {
                int d = divs[j];
                if (low <= d && d <= high) {
                    out.println(d);
                    continue lp;
                }
            }
            
            out.println(-1);
        }
        
        out.close();
    }

    int gcd(int a, int b) {
        while (a > 0 && b > 0)
            if (a > b)
                a %= b;
            else
                b %= a;
        return a + b;
    }
    
    /*************************************************************** 
     * Input 
     **************************************************************/
    String nextToken() throws IOException {
        while (!st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }
    
    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    
    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    
    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    
    String nextLine() throws IOException {
        st = new StringTokenizer("");
        return in.readLine();
    }
    
    boolean EOF() throws IOException {
        while (!st.hasMoreTokens()) {
            String s = in.readLine();
            if (s == null)
                return true;
            st = new StringTokenizer(s);
        }
        return false;
    }
}