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

public class Modified_GCD
{
	public static ArrayList<Long> ar = new ArrayList<Long>();
	public static HashSet<Long> hs = new HashSet<Long>();

	static class InputReader
	{
		BufferedReader br;
		public InputReader() throws IOException
		{
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		public int readInt() throws IOException
		{
			return Integer.parseInt(br.readLine());
		}
		public long readLong() throws IOException
		{
			return Long.parseLong(br.readLine());
		}
		public String readLine() throws IOException
		{
			return br.readLine();
		}
		public int[] readIntArray() throws IOException
		{
			return Arrays.asList(br.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
		}
		public long[] readLongArray() throws IOException
		{
			return Arrays.asList(br.readLine().split(" ")).stream().mapToLong(Long::parseLong).toArray();
		}
		public void close() throws IOException
		{
			br.close();
		}
	}
	public static void main(String[] args) throws IOException
	{
		InputReader br = new InputReader();
		PrintWriter pw = new PrintWriter(System.out);

		int test = 1;
		while(test--!=0)
		{
			long e[] = br.readLongArray();
			long r = e[0];

			long sqr = (long)Math.sqrt(r);
			for(long i=1;i<=sqr;i++)
			{
				if(r%i==0)
				{
					if(i==r/i)
						hs.add(i);
					else
					{
						hs.add(i);
						hs.add(r/i);
					}
				}
			}

			//System.out.println(hs);

			r = e[1];
			sqr = (long)Math.sqrt(r);
			for(long i=1;i<=sqr;i++)
			{
				if(r%i==0)
				{
					if(i==r/i)
					{
						if(hs.contains(i))
							ar.add(i);
					}
					else
					{
						if(hs.contains(i))
							ar.add(i);
						if(hs.contains(r/i))
							ar.add(r/i);
					}
				}
			}

			//System.out.println(ar);

			Collections.sort(ar);

			int q = br.readInt();
			while(q--!=0)
			{
				e = br.readLongArray();
				long val = getHighest(ar,e[0],e[1]);
				if(val>=e[0] && val<=e[1])
					pw.println(val);
				else
					pw.println("-1");
			}

		}
		pw.close();
		br.close();
	}

	public static long getHighest(ArrayList<Long> ar,long low ,long high)
	{
		int l = 0,r = ar.size()-1;
		int mid = 0;
		while(l<=r)
		{
			mid = (l+r)/2;
			if(ar.get(mid)<=low || ar.get(mid)<=high)
			{
				l = mid+1;
			}
			else if(ar.get(mid)>=high || ar.get(mid)>=low)
			{
				r = mid-1;
			}
			//System.out.println(l+" "+r);
		}

		return ar.get((l+r)/2);
	}
}