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.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * Created by timur on 28.03.15.
 */

public class TaskC {
    boolean eof;
    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

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

    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return "-1";
            }
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() {
        return Long.parseLong(nextToken());
    }

    double nextDouble() {
        return Double.parseDouble(nextToken());
    }

    String nextLine() throws IOException {
        return br.readLine();
    }


    void run() throws IOException {
        InputStream input = System.in;
        PrintStream output = System.out;
        try {
            File f = new File("a.in");
            if (f.exists() && f.canRead()) {
                input = new FileInputStream(f);
                output = new PrintStream("a.out");
            }
        } catch (Throwable e) {
        }
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(output);
        solve();
        br.close();
        out.close();
    }

    int gcdInt(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcdInt(b, a % b);
    }

    static Vector<Integer> v1, v2;

    static void getFactors(int n) {
        v1 = new Vector<Integer>();
        v2 = new Vector<Integer>();
        int d = 1, temp;
        for (int i = 2; i * i <= n; i += d, d = 2)
            if (n % i == 0) {
                v1.add(i);
                temp = 0;
                while (n % i == 0) {
                    n /= i;
                    temp++;
                }
                v2.add(temp);
            }
        if (n != 1) {
            v1.add(n);
            v2.add(1);
        }
    }

    static Vector<Integer> divisors;

    static void getDivisors(int ind, int res) {
        if (ind == (int) v1.size()) {
            divisors.add(res);
            return;
        }
        for (int i = 0; i <= v2.get(ind); i++) {
            getDivisors(ind + 1, res);
            res *= v1.get(ind);
        }
    }

    static Vector<Integer> getCDs(int a, int b) {
        getFactors(a);
        divisors = new Vector<Integer>();
        getDivisors(0, 1);
        Vector<Integer> d1 = divisors;
        getFactors(b);
        divisors = new Vector<Integer>();
        getDivisors(0, 1);
        Vector<Integer> d2 = divisors;
        Collections.sort(d1);
        Collections.sort(d2);
        Vector<Integer> cd = new Vector<Integer>();
        int i1 = 0, i2 = 0;
        while (i1 < d1.size() && i2 < d2.size()) {
            if (d1.get(i1).compareTo(d2.get(i2)) == 0) {
                cd.add(d1.get(i1));
                i1++;
                i2++;
            } else if (d1.get(i1).compareTo(d2.get(i2)) < 0)
                i1++;
            else
                i2++;
        }
        return cd;
    }

    static int upper_bound(Vector<Integer> v, int x) {
        int st = 0, en = v.size();
        while (st < en) {
            int md = (st + en) / 2;
            if (v.get(md) > x)
                en = md;
            else
                st = md + 1;
        }
        return st;
    }

    static void print(Vector<Integer> v) {
        System.out.print("{");
        for (int i = 0; i < v.size(); i++) {
            if (i > 0)
                System.out.print(", ");
            System.out.print(v.get(i));
        }
        System.out.println("}");
    }

    void solve() {
        int a = nextInt(), b = nextInt();
        int g = gcdInt(a, b);
        int n = nextInt();
        Vector<Integer> cd = getCDs(a, b);
        int low, high, ind;
        for (int i = 0; i < n; i++) {
            low = nextInt();
            high = nextInt();
            ind = upper_bound(cd, high);
            ind--;
            if (ind == -1 || cd.get(ind) < low)
                out.println(-1);
            else
                out.println(cd.get(ind));
        }
        out.close();
    }
}