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.*;
public class CF75C {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        StringBuffer sb = new StringBuffer();

        int A = Integer.parseInt(s[0]);
        int B = Integer.parseInt(s[1]);
        int c1 = 0;
        for(int i=1;i*i<=(Math.min(A, B));i++){
            if(A%i == 0 && B%i == 0){
                c1++;
                int k = A/i;
                if(A%k == 0 && B%k == 0){
                    c1++;
                }
                k = B/i;
                if(A%k == 0 && B%k == 0){
                    c1++;
                }
                continue;
            }
            if(B%i == 0){
                if(A%(B/i) == 0){
                    c1++;
                }
            }
            if(A%i == 0){
                if(B%(A/i) == 0){
                    c1++;
                }
            }
        }
        int[] a = new int[c1+1];
        int p = 0;
        for(int i=1;i*i<=(Math.min(A, B));i++){
            if(A%i == 0 && B%i == 0){
                a[p] = i;
                p++;
                int k = A/i;
                if(A%k == 0 && B%k == 0){
                    a[p] = k;
                    p++;
                }
                k = B/i;
                if(A%k == 0 && B%k == 0){
                    a[p] = k;
                    p++;
                }
                continue;
            }
            if(B%i == 0){
                if(A%(B/i) == 0){
                    a[p] = B/i;
                    p++;
                }
            }
            if(A%i == 0){
                if(B%(A/i) == 0){
                    a[p] = A/i;
                    p++;
                }
            }
        }
        if(A%Math.min(A, B) == 0 && B% Math.min(A, B) == 0){
            a[p] = Math.min(A, B);
        }else{
            a[p] = 1;
        }
        Arrays.sort(a);

        /*for(int app: a){
            System.out.println(app);
        }*/

        int q = Integer.parseInt(br.readLine());
        for(int i=0;i<q;i++){
            s = br.readLine().split(" ");
            int l = Integer.parseInt(s[0]);
            int r = Integer.parseInt(s[1]);
            int search = searchIndex(a, r);
            if(search >= l){
                sb.append(search+"\n");
            }else{
                sb.append(-1+"\n");
            }
        }



        System.out.println(sb);
    }
    private static int searchIndex(int[] a, int high){
        int l = 0;
        int r = a.length -1;
        int mid;
        while(true){
            if(a[r]  == high){
                return a[r];
            }else if(a[r] < high){
                return a[r];
            }else if(a[0] > high){
                return -1;
            }
            mid = (l+r)/2;
            if(l == mid || l == r){
                return a[l];
            }
            if(a[mid] == high){
                return high;
            }else if(a[mid] < high){
                l = mid;
            }else{
                r = mid;
            }
        }
    }
}