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.util.*;
import java.awt.geom.Point2D;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.*;
import java.math.BigInteger;
public class test {
   static int a,b,n,l,h;
   static List <Integer> factor = new ArrayList<Integer>();
	public static void main (String [] test) throws IOException   { 
	Scanner in = new Scanner(System.in);
	a=in.nextInt();b=in.nextInt();
	int gcd = gcd(a,b);
	factor(gcd);

	n= in.nextInt();
	int ans=0;
	for(int i = 0; i<n ; i++){
		l=in.nextInt();h=in.nextInt();
		int lo = 0 ; int hi = factor.size()-1;
		while(lo<=hi){
			int mid = lo+(hi-lo)/2;
			if(factor.get(mid)<=h){
				ans=factor.get(mid);
				lo=mid+1;
			}
			else{
				hi=mid-1;
			}
			
		}
		if(ans<l)ans=-1;
		
		System.out.println(ans);
		
	}

	
        


	}
	static int gcd (int n , int m){
		return m== 0 ? n : gcd(m,n%m);
		
	}
	static void factor (int n){
		for(int i = 1 ; i*i<=n; i++ ){
			if(n%i == 0){
				factor.add(i);
				if(i != n/i){
					factor.add(n/i);
				}
			}
		}
		Collections.sort(factor);
		
	}
	
	
}