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

/**
 * _75C
 * O(⌊√max(a,b)⌋*log(⌊√max(a,b)⌋) + n*log(⌊√max(a,b)⌋)) time
 * o(√n) space
 *
 * @author artyom
 */
public class _75C implements Runnable {
    private BufferedReader in;
    private PrintStream out;
    private StringTokenizer tok;

    private void solve() throws IOException {
        int a = nextInt(), b = nextInt(), g = gcd(a, b);
        List<Integer> ls = new LinkedList<>();
        for (int i = 1, sq = (int) Math.sqrt(g); i <= sq; i++) {
            if (g % i == 0) {
                ls.add(i);
            }
        }
        NavigableSet<Integer> divs = new TreeSet<>();
        for (int div : ls) {
            divs.add(div);
            divs.add(g / div);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1, n = nextInt(); i <= n; i++) {
            int l = nextInt(), r = nextInt();
            Integer x = divs.floor(r);
            sb.append(x == null || x < l ? -1 : x);
            if (i < n) {
                sb.append('\n');
            }
        }
        out.print(sb);
    }

    private static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new _75C().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = System.out;
            tok = null;
            solve();
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
}