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.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
// Some parts are totes unnecessary, but at this point
// the code's so ugly I'm afraid what removing anything 
// could do to it.

public class Mgcd {
    public static int floorBinSearch(Integer[] list, int v){
        int min = 0;
        int max = list.length -1;
        int hf;
        int curr;
        int currFloor = -1;
        while(min <= max){
            hf = min + (max - min)/2;
            curr = list[hf];
            if(curr == v){return v;}
            else if(curr > v){
                max = hf -1;
            }
            else{
                currFloor = curr;
                min = hf+1;
            }
        }
        return currFloor;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int a = Integer.parseInt(s[0]);
        int b = Integer.parseInt(s[1]);
        int n = Integer.parseInt(br.readLine());
        int gcd = a<=b?a:b, y = b>=a?b:a, r;
        while(y!=0){
            r = gcd%y;
            gcd = y; y = r;
        }
        int min = 1000000000, max = 0, lo, hi;
        HashMap<Integer,Integer> cache = new HashMap<Integer,Integer>();
        int[] los = new int[n];
        int[] his = new int[n];
        for (int i = 0; i < n; i++) {
            s = br.readLine().split(" ");
            lo = Integer.parseInt(s[0]);
            los[i] = lo;
            hi = Integer.parseInt(s[1]);
            his[i] = hi;
            min = lo<min?lo:min;
            max = hi>max?hi:max;
        }
        max = gcd<max?gcd:max;
        min = 2<min?min:2;
        ArrayList<Integer> cds = new ArrayList<Integer>();
        cds.add(1);
        double sq = Math.sqrt(gcd);
        for (int i = 2; i <= (int)sq && max!=1; i++) {
            if(gcd%i == 0){cds.add(i);}
        }
        int div1, div2;
        int siz = cds.size() - 1;
        for(int i = siz; i > 0; i--){
            div1 = cds.get(i);
            div2 = gcd/div1;
            cds.add(div2);
        }
        cds.add(gcd);
        Integer[] icds = cds.toArray(new Integer[cds.size()]);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int res;
            hi = his[i]; lo = los[i];
            if(cache.get(hi) == null){
                res = floorBinSearch(icds, hi);
                cache.put(hi, res);
            }
            else{
                res = cache.get(hi);
            }
            res = res<lo?-1:res;
            sb.append(res); sb.append("\n");
        }
        System.out.print(sb.toString());
    }
}