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.*;
public class GCD {
	static int[] p;
	static TreeSet<Integer> ad,bd;
	public static void main(String[] args){
		Scanner reader = new Scanner(System.in);
		int a = reader.nextInt();
		int b = reader.nextInt();
		p = fill();
		
		int n = reader.nextInt();
		ArrayList<Integer> af = pfactor(a);
		ArrayList<Integer> bf = pfactor(b);
		ad = new TreeSet<Integer>();
		bd = new TreeSet<Integer>();
		fill(1,0,af,ad);
		fill(1,0,bf,bd);
//		System.out.println(af + " " +ad);
//		System.out.println(bf + " " +bd);
		
		ad.retainAll(bd);
		for(int i = 0; i < n; i++){
			int low = reader.nextInt();
			int high = reader.nextInt();
			
			int ret = -1;
			if(ad.floor(high) != null && ad.floor(high) >= low)
				ret = ad.floor(high);
			System.out.println(ret);
		}
	}
	
	public static void fill(int n, int p, ArrayList<Integer> f, TreeSet<Integer> s){
		if(p == f.size()){
			s.add(n);
			return;
		}
		
		int t = p;
		for(int i = p; i < f.size() && f.get(i)==f.get(p); i++)
			t++;
		
		fill(n,t,f,s);
		int curry = 1;
		for(int i = p; i < f.size() && f.get(i)==f.get(p); i++){
			curry *= f.get(i);
			fill(n*curry, t, f, s);
		}
	}
	
	public static ArrayList<Integer> pfactor(int x){
		ArrayList<Integer> ret = new ArrayList<Integer>();
		for(int i = 0; x > 1 && i < p.length; i++){
			while(x%p[i]==0){
				ret.add(p[i]);
				x/=p[i];
			}
		}		
		if(x > 1)
			ret.add(x);
		return ret;
	}
	
	public static int[] fill(){
		boolean[] sieve = new boolean[1000001];
		Arrays.fill(sieve, true);
		sieve[0] = false;
		sieve[1] = false;
		int n = 0;
		for(int i = 0; i < sieve.length; i++){
			if(sieve[i]){
				n++;
				for(int j = i*i; i < 1002 && j < sieve.length; j+=i)
					sieve[j] = false;
			}
		}
		
		int[] p = new int[n];
		n = 0;
		for(int i = 0; i < sieve.length; i++)
			if(sieve[i])
				p[n++] = i;
		return p;
	}
}