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.util.*;

public class C{     
        
        private BufferedReader in;  
        private StringTokenizer st;
        
        ArrayList<Integer> primes = new ArrayList<Integer>();
        ArrayList<Integer> occ = new ArrayList<Integer>();
        ArrayList<Integer> divisors = new ArrayList<Integer>();
        void solve() throws IOException{
            
            int a = nextInt();
            int b = nextInt();
            int gcd = gcd(a,b);
            factor(gcd);
            Collections.sort(divisors);         
            int n = nextInt();
            for (int i = 0; i < n; i++) {
                int l = nextInt();
                int h = nextInt();
                System.out.println(get(l,h));
            }
        }
        
        int get(int l,int h){
            
            int res = -1;
            int st = 0;
            int end = divisors.size() - 1;
            int mid = (st + end)/2;
            while(st<=end){
                                
                if(divisors.get(mid)>=l && divisors.get(mid)<=h){
                    res = divisors.get(mid);
                    st = mid + 1;
//                  return divisors.get(mid);
                }
                else if(divisors.get(mid)<l){
                    st = mid + 1;
                }
                else if(divisors.get(mid)>h){
                    end = mid - 1;
                }
                
                mid = (st + end)/2;
            }
            return res;
        }
            

        void factorize(int n){
            
            if(n%2==0){
                primes.add(2);
                occ.add(0);
                while(n%2==0){
                    n/=2;
                    occ.set(occ.size()-1, occ.get(occ.size()-1) + 1);
                }
            }
            for (int i = 3; i <= Math.sqrt(n) + 1; i+=2) {
                if(n%i==0){
                    primes.add(i);
                    occ.add(0);
                    while(n%i==0){
                        n/=i;
                        occ.set(occ.size()-1, occ.get(occ.size()-1) + 1);
                    }               
                }
            }
            if(n!=1){
                primes.add(n);
                occ.add(1);
            }
            
        }
        void generateDivisors(int i,int d){
            if(i==primes.size()){
                divisors.add(d);
                return;
            }
            for (int j = 0; j <= occ.get(i); j++) {
                generateDivisors(i+1, d*(int)Math.pow(primes.get(i), j));
            }
            
        }
        void factor(int n){
            
            
            primes = new ArrayList<Integer>();
            occ = new ArrayList<Integer>();
            divisors = new ArrayList<Integer>();
            factorize(n);
            generateDivisors(0,1);          
            
        }
        C() throws IOException {
            in = new BufferedReader(new InputStreamReader(System.in));          
            eat("");
            solve();            
        }

        private void eat(String str) {
            st = new StringTokenizer(str);
        }

        String next() throws IOException {
            while (!st.hasMoreTokens()) {
                String line = in.readLine();
                if (line == null) {
                    return null;
                }
                eat(line);
            }
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public static void main(String[] args) throws IOException {
            new C();
        }

        int gcd(int a,int b){
            if(b>a) return gcd(b,a);
            if(b==0) return a;
            return gcd(b,a%b);
        }

}