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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Vector;

public class gdc {
	
	public static Vector<Integer> divisors(int a) {
		Vector<Integer> v = new Vector<Integer>();
		for (int i=1;i<=Math.sqrt(a);i++) {
			if (a%i==0) {
				v.add(i);
				if (a/i!=i)
					v.add(a/i);
			}
		}
		Collections.sort(v);
		return v;
	}
	
	public static Integer[] cd(int a, int b) {
		Vector<Integer> v = new Vector<Integer>();
		Vector<Integer> va = divisors(a);
		Vector<Integer> vb = divisors(b);
		for (int i=0;i<va.size();i++) {
			if (vb.contains(va.elementAt(i))) {
				v.add(va.elementAt(i));
			}
		}
		return v.toArray(new Integer[v.size()]);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] line = in.readLine().split(" ");
		int a = Integer.parseInt(line[0]);
		int b = Integer.parseInt(line[1]);
		int q = Integer.parseInt(in.readLine());
		Integer[] cds = (Integer[]) cd(a,b);
		for(int i=0;i<q;i++) {
			String[] x = in.readLine().split(" ");
			int min = Integer.parseInt(x[0]);
			int max = Integer.parseInt(x[1]);
			int indexmin = 0;
			while ((indexmin < cds.length) && cds[indexmin]<min) {
				indexmin++;
			} 
			int indexmax = cds.length-1;
			while ((indexmax >= 0) && cds[indexmax]>max) {
				indexmax--;
			}
			if (indexmin>indexmax) {
				System.out.println("-1");
			} else {
				System.out.println(cds[indexmax]);
			}
		}
		
	}
}