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 Solution {

    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer st;

    public String next() throws Exception {
        if (st == null || !st.hasMoreElements()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(next());
    }
    public long nextLong() throws Exception {
        return Long.parseLong(next());
    }
    public double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }

    public List<Integer> getDivisors(int n) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i * i <= n; ++i) {
            if (n % i == 0) {
                int d = n / i;
                if (d != i) list.add(d);
                list.add(i);
            }
        }
        Collections.sort(list);
        return list;
    }

    public void run() throws Exception {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        int a = nextInt();
        int b = nextInt();
        List<Integer> da = getDivisors(a);
        List<Integer> db = getDivisors(b);
        List<Integer> d = new ArrayList<Integer>();
        int i = 0;
        int j = 0;
        while(i < da.size() && j < db.size()) {
            if (da.get(i).equals(db.get(j))) {
                d.add(da.get(i));
                ++i;
                ++j;
            } else if (da.get(i) > db.get(j)) {
                ++j;
            } else {
                ++i;
            }
        }
        // System.out.println(Arrays.toString(da.toArray()));
        // System.out.println(Arrays.toString(db.toArray()));
        // System.out.println(Arrays.toString(d.toArray()));
        int n = nextInt();

        for (int t = 0; t < n; ++t) {
            int l = nextInt();
            int r = nextInt();
            boolean ok = false;
            for(i = d.size() - 1; i >= 0; --i) {
                if (l <= d.get(i) && d.get(i) <= r) {
                    out.println(d.get(i));
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                out.println(-1);
            }

        }
        out.close();
    }

    public static void main(String[] args) throws Exception {
        new Solution().run();
    }
}