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:
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Ideone
{
    static ArrayList<Integer> d1=new ArrayList<Integer>();
    static ArrayList<Integer> d2=new ArrayList<Integer>();
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner sc=new Scanner(System.in);
        
        BufferedWriter bf=new BufferedWriter(new OutputStreamWriter(System.out));
        
        PrintWriter cout = new PrintWriter(bf);
        
        int a=sc.nextInt();
        int b=sc.nextInt();
        
        caldiv(d1,a);
        caldiv(d2,b);
        Collections.sort(d1);
        Collections.sort(d2);
        ArrayList<Integer> g = gcd(d1,d2);
        
        int n=sc.nextInt();
        //System.out.println(n);
        for(int i=0;i<n;i++)
        {
            //System.out.println(i);
            int l=sc.nextInt();
            int r=sc.nextInt();
            
            int ind = upper_bound(g,r);
            ind--;
            
            if(ind==-1 || g.get(ind)<l)
            {
                System.out.println(-1);
            }
            else
            {
                 System.out.println(g.get(ind));
            }
        }
        
    }
    static int upper_bound(ArrayList<Integer>g, int x )
    {
        int st = 0;
        int en = g.size();
        while(st<en)
        {
            int m=(st+en)/2;
            if(g.get(m) > x)
            {
                en=m;
            }
            else
            {
                st=m+1;
            }
        }
        return st;
        
    }
    public static ArrayList<Integer> gcd(ArrayList<Integer> d1, ArrayList<Integer> d2)
    {
        int l1=d1.size();
        int l2=d2.size();
        int i=0,j=0;
        ArrayList<Integer> d3=new ArrayList<Integer>();
        while(i<l1 && j<l2)
        {
            if(d1.get(i).compareTo(d2.get(j))==0)
            {
                d3.add(d1.get(i));
                i++;
                j++;
            }
            else if(d1.get(i).compareTo(d2.get(j))<0)
            {
                i++;
            }
            else
            {
                j++;
            }
        }
        
        return d3;
    }
    
    public static void caldiv(ArrayList<Integer> d1 , int a)
    {
        int i;
        for(i=1;i<Math.sqrt(a);i++)
        {
            if(a%i==0)
            {
                d1.add(i);
                d1.add(a/i);
            }
        }
        if(i*i==a)
        {
            d1.add(i);
        }
    }
    
    
}