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.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;
 
public class modified_gcd_ahmed_java_ac {
 
        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("}");
        }
 
        public static void main(String[] args) {
                BufferedReader bfin = new BufferedReader(new InputStreamReader(
                                System.in));
                BufferedWriter bfout = new BufferedWriter(new OutputStreamWriter(
                                System.out));
                Scanner cin = new Scanner(bfin);
                PrintWriter cout = new PrintWriter(bfout);
                int a, b, n;
                a = cin.nextInt();
                b = cin.nextInt();
                Vector<Integer> cd = getCDs(a, b);
                n = cin.nextInt();
                int low, high, ind;
                for (int i = 0; i < n; i++) {
                        low = cin.nextInt();
                        high = cin.nextInt();
                        ind = upper_bound(cd, high);
                        ind--;
                        if (ind == -1 || cd.get(ind) < low)
                                cout.println(-1);
                        else
                                cout.println(cd.get(ind));
                }
                cout.close();
        }
}