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.*;
import java.io.*;
import java.math.*;

public class Main {

	static class FastScanner {
		BufferedReader s;
		StringTokenizer st;

		public FastScanner(InputStream InputStream) {
			st = new StringTokenizer("");
			s = new BufferedReader(new InputStreamReader(InputStream));
		}

		public FastScanner(File f) throws FileNotFoundException {
			st = new StringTokenizer("");
			s = new BufferedReader(new FileReader(f));
		}

		public int nextInt() throws IOException {
			if (st.hasMoreTokens())
				return Integer.parseInt(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextInt();
			}
		}

		public BigInteger big() throws IOException {
			if (st.hasMoreTokens())
				return new BigInteger(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return big();
			}
		}

		public double nextDouble() throws IOException {
			if (st.hasMoreTokens())
				return Double.parseDouble(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextDouble();
			}
		}

		public long nextLong() throws IOException {
			if (st.hasMoreTokens())
				return Long.parseLong(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextLong();
			}
		}

		public String next() throws IOException {
			if (st.hasMoreTokens())
				return st.nextToken();
			else {
				st = new StringTokenizer(s.readLine());
				return next();
			}

		}

		public String nextLine() throws IOException {
			return s.readLine();
		}

		public void close() throws IOException {
			s.close();
		}

	}
	
	public static void main(String[] args) throws java.lang.Exception {
		FastScanner in = new FastScanner(System.in);
		int a = in.nextInt(), b = in.nextInt();
		if(a > b) {
			int tep = a;
			a = b;
			b = tep;
		}
		int g = gcd(a, b);
		ArrayList <Integer> list1 = new ArrayList();
		ArrayList <Integer> list2 = new ArrayList();
		for(int x = 1; x * x <= g; x++) {
			if(g % x == 0) {
				list1.add(x);
				list2.add(g / x);
			}
		}
		for(int x = list2.size() - 1; x >= 0; x--) 
			list1.add(list2.get(x));
		StringBuilder sb  = new StringBuilder("");  
		int q = in.nextInt();
		while(q-- > 0) {
			int l = in.nextInt(), r = in.nextInt();
			int st = 0, end = list1.size() - 1;
			int ans = -1;
			while(st <= end) {
				int mid = (end - st) / 2 + st;
				int val = list1.get(mid);
				if(val >= l && val <= r) {
					ans = val;
					st = mid + 1;
				}
				else if(val < l) {
					st = mid + 1;
				}
				else {
					end = mid - 1;
				}
			}
			sb.append(ans + "\n");
		}
		System.out.print(sb);
	}
	private static int gcd(int a, int b) {
		if(a == 0 || b == 0) {
			return (a|b);
		}
		while(a/b*b != a) {
			int temp = b;
			b = a%b;
			a = temp;
		}
		return b;
	}
}