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.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

/**
 * Date 20.11.2011 
 * Time 23:05:45 
 * Author Woodey 
 * $
 */

public class C75 {
	private void Solution() throws IOException {
		int a = nextInt(), b = nextInt();
		ArrayList<Integer> nod = commonDevides(devides(a), devides(b));
		int n = nextInt(), m = nod.size();
		Collections.sort(nod);
		while (n -- > 0) {
			int low = nextInt(), high = nextInt();
			for (int i = m-1; i >= 0; i --) {
				int next = nod.get(i);
				if (next >= low && next <= high) {
					System.out.println(next);
					break;
				}
				if (i == 0)
					System.out.println("-1");
			}
		}
	}

	ArrayList<Integer> devides(int n) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		for (int i = 1; i * i <= n; i ++) {
			if (n % i == 0) {
				res.add(i);
				if (i * i != n)
					res.add(n / i);
			}
		}
		return res;
	}

	ArrayList<Integer> commonDevides(ArrayList<Integer> a, ArrayList<Integer> b) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		HashSet<Integer> set = new HashSet<Integer>();
		for (int i = 0; i < a.size(); i ++)
			set.add(a.get(i));
		for (int i = 0; i < b.size(); i ++) {
			int next = b.get(i);
			if (set.contains(next)) {
				res.add(next);
			}
		}
		return res;
	}

	public static void main(String[] args) {
		new C75().run();
	}

	BufferedReader in;
	StringTokenizer tokenizer;

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			Solution();
			in.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(in.readLine());
		return tokenizer.nextToken();
	}
}