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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int INPUT_BUFF = (1<<15);
    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
        InputReader(InputStream is) {
            reader = new BufferedReader(new InputStreamReader(is), INPUT_BUFF);
            tokenizer = null;
        }

        String next() {
            while(tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    static int gcd(int a, int b) {
        while(b > 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

    static void solve() {
        int a = in.nextInt(), b = in.nextInt();
        List<Integer> arr = new ArrayList<>();
        int g = gcd(a, b);
        for(int i = 1; i*i <= g; i++) {
            if(g%i == 0) {
                int j = g / i;
                arr.add(i);
                if(j != i) arr.add(j);
            }
        }
        Collections.sort(arr);
        int n = in.nextInt();
        while(n > 0) {
            int low = in.nextInt(), high = in.nextInt(), res = -1;
            int l = 0, h = arr.size() - 1;
            while(l < h) {
                int m = (l + h) >> 1;
                if(arr.get(m) <= high) {
                    l = m + 1;
                } else h = m;
            }
            if(arr.get(l) > high) l--;
            if(l >= 0) {
                if(arr.get(l) >= low) {
                    res = arr.get(l);
                }
            }
            out.println(res);
            n--;
        }
    }
    public static void main(String[] args) {
        int tests = 1;
//        tests = in.nextInt();
        for(int i = 1; i <= tests; i++) {
            solve();
        }
        out.close();
    }
}