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 A {
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		PrintWriter pw=new PrintWriter(System.out);
		
		ArrayList<Integer> common=new ArrayList<Integer>();
		int a=sc.nextInt();
		int b=sc.nextInt();
		ArrayList<Integer> d=new ArrayList<Integer>();
		for(int i=1;i*i<=a;i++){
			if(a%i==0){
				d.add(i);
				if(i!=a/i)
					d.add(a/i);
			}
		}
		for(int i : d)
			if(b%i==0)
				common.add(i);
		Collections.sort(common);
		int t=sc.nextInt();
		int n=common.size();
		while(t-->0){
			int l=sc.nextInt();
			int r=sc.nextInt();
			int start=0,end=n-1,ans=-1;
			while(start<=end){
				int mid=((start+end)>>1);
				if(common.get(mid)<=r){
					ans=common.get(mid);
					start=mid+1;
				}else
					end=mid-1;
			}
			pw.println(ans>=l? ans : -1);
		}
		pw.flush();
		pw.close();
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {br = new BufferedReader(new InputStreamReader(System.in));}
		String next() {while (st == null || !st.hasMoreElements()) {
			try {st = new StringTokenizer(br.readLine());}
			catch (IOException e) {e.printStackTrace();}}
		return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
	}
}