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.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main 
{
	static int gcd(int a, int b)
	{
		return b==0? a:gcd(b, a%b);
	}
	public static void main(String[] args) 
	{
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
		while(in.hasNext())
		{
			int a=in.nextInt();
			int b=in.nextInt();
			int g=gcd(a, b);
			ArrayList<Integer> v=new ArrayList<Integer>();
			v.clear();
			for(int i=1;i*i<=g;i++)
				if(g%i==0)
				{
					v.add(i);
					if(g/i>i)
						v.add(g/i);
				}
			Collections.sort(v);
//			for(int i=0;i<v.size();i++)
//				System.out.println(v.get(i));
			int q=in.nextInt();
			while((q--)!=0)
			{
				int l=in.nextInt();
				int r=in.nextInt();
				int ans=-1;
				for(int i=0;i<v.size();i++)
					if(l<=v.get(i) && v.get(i)<=r)
						ans=v.get(i);
				out.println(ans);
			}
		}
		out.close();
	}
}

class InputReader 
{
	BufferedReader buf;
	StringTokenizer tok;
	InputReader() 
	{
		buf = new BufferedReader(new InputStreamReader(System.in));
	}

	boolean hasNext() 
	{
		while (tok == null || !tok.hasMoreElements()) 
		{
			try 
			{
				tok = new StringTokenizer(buf.readLine());
			} 
			catch (Exception e) 
			{
				return false;
			}
		}
		return true;
	}

	String next() 
	{
		if (hasNext())
			return tok.nextToken();
		return null;
	}

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

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

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

	BigInteger nextBigInteger() 
	{
		return new BigInteger(next());
	}

	BigDecimal nextBigDecimal() 
	{
		return new BigDecimal(next());
	}
}