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.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class ModifiedGCD {

	static class node implements Comparable<node> {
		long p;
		int c;

		node(long p, int c) {
			this.p = p;
			this.c = c;
		}

		@Override
		public int compareTo(node o) {
			return (int) (o.p - p);
		}

	}

	static ArrayList<Long> p = new ArrayList<>();
	static node[] x;
	static HashMap<Long, Integer> hm;
	static ArrayList<Long> div = new ArrayList<>();

	static HashMap<Long, Integer> fact(long x) {
		HashMap<Long, Integer> hm = new HashMap<>();
		int idx = 0;
		long prim = p.get(idx++);
		while (x != 1 && prim * prim <= x) {
			if (x % prim == 0) {
				int cnt = 0;
				while (x % prim == 0) {
					x /= prim;
					cnt++;
				}
				hm.put(prim, cnt);
			}
			prim = p.get(idx++);
		}
		if (x != 1)
			hm.put(x, 1);
		return hm;
	}

	static void generate(int idx, long num) {
		if (idx == x.length) {
			div.add(num);
			return;
		}
		generate(idx + 1, num);
		if (hm.containsKey(x[idx].p)) {
			int min = Math.min(x[idx].c, hm.get(x[idx].p));
			long res = 1;
			for (int i = 1; i <= min; i++) {
				res *= x[idx].p;
				generate(idx + 1, num * res);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		sc = new StringTokenizer("");
		boolean[] v = new boolean[40000];
		for (long i = 2; i < v.length; i++) {
			if (!v[(int) i]) {
				p.add(i);
				for (long j = i * i; j < v.length; j += i)
					v[(int) j] = true;
			}
		}
		long a = nxtLng();
		long b = nxtLng();
		hm = fact(a);
		x = new node[hm.size()];
		int idx = 0;
		for (Long l : hm.keySet())
			x[idx++] = new node(l, hm.get(l));
		Arrays.sort(x);
		hm = fact(b);
		generate(0, 1);
		Collections.sort(div);
		int n = nxtInt();
		while (n-- > 0) {
			long x = nxtLng();
			long y = nxtLng();
			int l = 0;
			int r = div.size() - 1;
			while (l < r) {
				int mid = (l + r) / 2;
				if (div.get(mid) < y)
					l = mid + 1;
				else
					r = mid;
			}
			if (r > 0 && div.get(r) > y)
				r--;
			out.println(div.get(r) >= x && div.get(r) <= y ? div.get(r) : -1);
		}
		br.close();
		out.close();
	}

	static BufferedReader br;
	static StringTokenizer sc;
	static PrintWriter out;

	static String nxtTok() throws IOException {
		while (!sc.hasMoreTokens()) {
			String s = br.readLine();
			if (s == null)
				return null;
			sc = new StringTokenizer(s.trim());
		}
		return sc.nextToken();
	}

	static int nxtInt() throws IOException {
		return Integer.parseInt(nxtTok());
	}

	static long nxtLng() throws IOException {
		return Long.parseLong(nxtTok());
	}

	static double nxtDbl() throws IOException {
		return Double.parseDouble(nxtTok());
	}

	static int[] nxtIntArr(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nxtInt();
		return a;
	}

	static long[] nxtLngArr(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nxtLng();
		return a;
	}

	static char[] nxtCharArr() throws IOException {
		return nxtTok().toCharArray();
	}
}