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.lang.*;
import java.util.*;
import java.math.*;
 
public class code
{
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 

     static class FastWriter
    {
        OutputStream os;

        public FastWriter()
        {
            os = new BufferedOutputStream(System.out);
        }

        void println(String content)throws IOException
        {
            print(content);
            print("\n");
        }

        void print(String content)throws IOException
        {
            os.write(content.getBytes());
        }

        void flush()throws IOException
        {
            os.flush();
        }
    }
    
    static long P = 1000000007L;
    public static void main(String args[])throws IOException
    {
        FastReader scn = new FastReader();

        long a = scn.nextLong();
        long b = scn.nextLong();

        long gcd = getGCD(a, b);
        ArrayList<Long> factors = new ArrayList<>();

        for(long i = 1; i <= Math.sqrt(gcd) + 1; i++)
        {
            if(gcd%i != 0)
                continue;

            long factor_1 = i;
            long factor_2 = gcd/i;

            if(factor_1 == factor_2)
            {
                factors.add(factor_1);
            }
            else if(factor_1 < factor_2)
            {
                factors.add(factor_1);
                factors.add(factor_2);
            }
        }

        int k = scn.nextInt();
        int size = factors.size();
        Collections.sort(factors);

        while(k-- > 0)
        {
            long low = scn.nextLong();
            long high = scn.nextLong();

            int index = getLessThanIndex(factors, high, 0, size - 1);
            if(index == -1)
                System.out.println(-1);
            else if(factors.get(index) >= low)
                System.out.println(factors.get(index));
            else
                System.out.println(-1);
        }

    }

    public static long getGCD(long a, long b)
    {
        if(a==b || b==0)
            return a;

        if(a==0)
            return b;

        if(a < b)
            return getGCD(a, b%a);
        else
            return getGCD(b, a%b);
    }

    public static int getLessThanIndex(ArrayList<Long> list, long value, int l, int r)
    {
        while( l <= r)
        {
            int middle = (l+r)/2;
 
            if(list.get(middle) == value)
                return middle;
            else if(list.get(middle)< value)
                l = middle + 1;
            else
                r = middle - 1;
        } 
        return r;
    }

    // public static long dfs(Node current, int l, int r, Node[] nodes)
    // {
    //     current.visited = true;
        
    //     long ans = 1;
    //     for(Node next: current.neighbors)
    //     {
    //         if(!next.visited && next.sorted_index <= r && next.sorted_index >= l)
    //         {
    //             long p = dfs(next, l, r, nodes);
    //             ans = (ans * ( p + 1))%P;
    //         }
    //     }

    //     current.visited = false;
    //     return ans;
    // }
}

class Pair
{
    int a, b;
    public Pair(int a, int b)
    {
        this.a = a;
        this.b = b;
    }
}

// class Node implements Comparable<Node>
// {
//     int weight;
//     int sorted_index;
//     ArrayList<Node> neighbors;
//     boolean visited;
//     public Node()
//     {
//         neighbors = new ArrayList<>();
//     }

//     public int compareTo(Node n)
//     {
//         return this.weight - n.weight;
//     }
 
// }
 
// class MutableInt
// {
//     int count;
//     ArrayList<Integer> list;
//     public MutableInt()
//     {
//         list = new ArrayList<>();
//     }
// }

// class TrieNode
// {
//     HashMap<Character, TrieNode> map;
//     boolean visited;
//     int cost;

//     public TrieNode()
//     {
//         map = new HashMap<>();
//     }

//     public TrieNode add(char c, boolean isGood, MutableInt result, int k)
//     {
//         if(map.containsKey(c))
//         {
//             TrieNode n = map.get(c);
//             return n;
//         }
//         else
//         {
//             TrieNode n = new TrieNode();
//             if(!isGood)
//                 n.cost = this.cost + 1;
//             else
//                 n.cost = this.cost;

//             if(n.cost <= k)
//                 result.count = result.count + 1;

//             map.put(c, n);
//             return n;
//         }
//     }
// }