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.*;
import java.math.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;
   

public class Main {
            
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                                            //(new FileReader("input.in"));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;
        Reader.init(System.in);
        //PrintWriter pw = new PrintWriter("output.out", "UTF-8");
        
        tk = new StringTokenizer(in.readLine());
        int a = parseInt(tk.nextToken()),b = parseInt(tk.nextToken());
        int i,cnt=0,MAX = 40000;
        
        int [] da = new int[MAX],d = new int[MAX];
        Arrays.fill(da, Integer.MAX_VALUE);
        Arrays.fill(d, Integer.MAX_VALUE);
        
        for(i=1; i*i<=a; i++) {
            if(a%i == 0) {
                da[cnt++] = i;
                if(i != a/i)
                    da[cnt++] = a/i;
            }
        }
        Arrays.sort(da,0,cnt);
                
        cnt = 0;
        for(i=1; i*i<=b; i++) {
            if(b%i == 0) {
                if(Arrays.binarySearch(da, i) >= 0)
                    d[cnt++] = i;
                if(i != b/i && Arrays.binarySearch(da, b/i) >= 0) 
                    d[cnt++] = b/i;
            }
        }
        Arrays.sort(d,0,cnt);
        
      
        
        int q = parseInt(in.readLine());
        int l,r;
        
        while(q-- > 0) {
            tk = new StringTokenizer(in.readLine());
            l = parseInt(tk.nextToken());
            r = parseInt(tk.nextToken());
            
            for(i=cnt-1; i>=0; i--) {
                if(d[i]>=l && d[i]<=r)
                    break;
            }
            
            out.append(i<0 ? -1 : d[i]).append("\n");
        }
        
        System.out.print(out);
    }
    
}

class Tools {
    
    public static boolean next_permutation(int [] p,int len) {
        int a =len-2;
        while(a>=0 && p[a]>=p[a+1])
            a--;
        
        if(a==-1)
            return false;
        
        int b = len-1;
        while(p[b]<=p[a])
            b--;
        
        p[a] += p[b];
        p[b] = p[a] - p[b];
        p[a] -= p[b];
        
        for(int i=a+1, j=len-1; i<j; i++,j--) {
            p[i] += p[j];
            p[j] = p[i]-p[j];
            p[i] -= p[j];
        }
        
        return true;
    }
    
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) throws UnsupportedEncodingException {
        reader = new BufferedReader(
                     new InputStreamReader(input, "UTF-8") );
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
    
    static String nextLine() throws IOException {
        return reader.readLine();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
    
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
}