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.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;


public class problemC implements Runnable{
    
    public void solve() throws IOException{
        int[] par=intArr();
        int a=par[0];
        int b=par[1];
        HashSet<Integer> allDiv=new HashSet<Integer>();
        for(int i=1;i*i<=Math.min(a, b);i++){
            if(a%i==0 && b%i==0){
                allDiv.add(i);
            }
            if(a%i==0){
                int d=a/i;
                if(b%d==0){
                    allDiv.add(d);
                }
            }
            if(b%i==0){
                int d=b/i;
                if(a%d==0){
                    allDiv.add(d);
                }
            }
        }
        Integer[] div=allDiv.toArray(new Integer[0]);
        Arrays.sort(div);
        
        
        
        int n=intArr()[0];
        for(int i=0;i<n;i++){
            par=intArr();
            out.println(maxDiv(div, par[0], par[1]));
        }
    }
    
    private int maxDiv(Integer[] div, int low, int high){
        //binary search
        int i1=0;
        int i2=div.length;
        int ii;
        while(i2>i1){
            ii=(i1+i2)/2;
            if(div[ii]<low){
                i1=ii+1;
            } else if(div[ii]>high){
                i2=ii;
            } else if(ii==div.length-1 || div[ii+1]>high){
                return div[ii];
            } else {
                i1=ii;
            }
        }
        return -1;
    }

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

    @Override
    public void run(){
//      System.out.println("trying to solve");
        try{
            in=new BufferedReader(new InputStreamReader(stdin));
            out=new PrintWriter(stdout);
            solve();
            in.close();
            out.close();
        } catch (Exception ex){
            ex.printStackTrace();
            System.exit(1);
        }
    }
    
    BufferedReader in;
    PrintWriter out;
    
    int[] intArr() throws IOException {
        String[] arr=nextLine().split("\\s");
        int[] res=new int[arr.length];
        for(int i=0;i<arr.length;i++) res[i]=Integer.parseInt(arr[i]);
        return res;
    }

    long[] longArr() throws IOException {
        String[] arr=nextLine().split("\\s");
        long[] res=new long[arr.length];
        for(int i=0;i<arr.length;i++) res[i]=Long.parseLong(arr[i]);
        return res;
    }

    double[] doubleArr() throws IOException {
        String[] arr=nextLine().split("\\s");
        double[] res=new double[arr.length];
        for(int i=0;i<arr.length;i++) res[i]=Double.parseDouble(arr[i]);
        return res;
    }

    String nextLine() throws IOException {
        return in.readLine();
    }
    
    InputStream stdin;
    OutputStream stdout;
    public problemC(){
        stdin=System.in;
        stdout=System.out;
    }
    
    public problemC(InputStream stdin, OutputStream stdout){
        this.stdin=stdin;
        this.stdout=stdout;
    }
}