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 round67;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class C {

	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static PrintWriter out = new PrintWriter(System.out);
	
	static String nextToken() throws IOException{
		while (st==null || !st.hasMoreTokens()){
			String s = bf.readLine();
			if (s == null)
				return null;
			st = new StringTokenizer(s);
		}
		
		return st.nextToken();
	}
	
	static int nextInt() throws IOException{
		return Integer.parseInt(nextToken());
	}
	
	static long nextLong() throws IOException{
		return Long.parseLong(nextToken());
	}
	
	static String nextStr() throws IOException{
		return nextToken();
	}
	
	static double nextDouble() throws IOException{
		return Double.parseDouble(nextToken());
	}
	
	static int gcd(int a, int b){
		if (a == 0)
			return b;
		return gcd(b%a, a);
	}
	
	public static void main(String[] args) throws IOException{
		int a = nextInt(),
			b = nextInt(),
			g = gcd(a, b),
			n = nextInt();
		
		int k = 0;
		int s[] = new int[10000];
		for (int i=1; i*i<=g; i++)
			if (g%i == 0){
				s[k++] = i;
				s[k++] = g/i;
			}
		
		for (int q=0; q<n; q++){
			int l = nextInt(),
				r = nextInt();
			
			int max = -1;
			for (int i=0; i<k; i++)
				if (s[i]>=l && s[i]<=r && s[i]>max)
					max = s[i];
			
			out.println(max);
		}
		
		out.flush();
	}

}