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

public class F {

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int a = sc.nextInt(), b = sc.nextInt(), g = gcd(a, b);
		ArrayList<Integer> divs = new ArrayList<Integer>();
		for(int i = 1; i * i <= g; ++i)
			if(g % i == 0)
			{
				divs.add(i);
				if(i != g / i)
					divs.add(g / i);
			}
		Collections.sort(divs);
		int q = sc.nextInt();
		while(q-->0)
		{
			int l = sc.nextInt(), r = sc.nextInt();
			int ans = -1, lo = 0, hi = divs.size() - 1;
			while(lo <= hi)
			{
				int mid = lo + hi >> 1;
				if(divs.get(mid) <= r)
				{
					ans = divs.get(mid);
					lo = mid + 1;
				}
				else
					hi = mid - 1;
			}
			if(ans < l)
				ans = -1;
			out.println(ans);
		}
		out.close();
	}
	
	static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

		public long nextLong() throws IOException {return Long.parseLong(next());}

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

		public double nextDouble() throws IOException { return Double.parseDouble(next()); }

		public boolean ready() throws IOException {return br.ready();}
	}
}