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 //do not write package name here */

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

public class codeforces {
    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 int gcd(int a,int b)
    {
        if(a==0)
            return b;
        else return gcd(b%a,a);
    }
    static int binary(int low,int high,ArrayList<Integer> al,int key)
    {
        int ans=-1;
        while(low<=high){
            int mid=low+(high-low)/2;
            if(key<al.get(mid))
                high=mid-1;
            else {
                ans = al.get(mid);
                low = mid + 1;
            }

        }
        return ans;

    }
    public static void main(String[] args){

        FastReader sc = new FastReader();
        int a=sc.nextInt();
        int b= sc.nextInt();
        int q=sc.nextInt();
        ArrayList<Integer> al=new ArrayList<>();
        int gcd=gcd(a,b);
        for(int i=1;i*i<=gcd;i++)
        {
            if(gcd%i==0)
            {
                if(i*i==gcd)
                    al.add(i);
                else{
                    al.add(i);
                    al.add(gcd/i);
                }
            }
        }
        Collections.sort(al);
        while(q-->0)
        {
            int low=sc.nextInt();
            int high=sc.nextInt();
            int ans=binary(0,al.size()-1,al,high);
            if(ans==-1|| ans<low)
                System.out.println(-1);
            else
                System.out.println(ans);
        }
    }
}