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.*;
public class Con1{
	
	public static void main(String args[]) throws IOException {
	Scanner sc=new Scanner(System.in);
	int a=sc.nextInt();
	int b=sc.nextInt();
TreeSet<Integer> set=new TreeSet<>();
HashSet<Integer > l=new HashSet<>();
ArrayList<Integer > l1=new ArrayList<>();

for (int i=1; i<=Math.sqrt(a); i++) 
    { 
        if (a%i==0) 
        { 
            if (a/i == i) 
            	l.add(i);
   
            else // Otherwise print both 
            	l.add(a/i);
            l.add(i);
        } 
    }
for (int i=1; i<=Math.sqrt(b); i++) 
{ 
    if (b%i==0) 
    { 
        if (b/i == i) { 
        	if(l.contains(i)) {
        		set.add(i);
        	}
        
        }

        else {// Otherwise print both 
        if(l.contains(b/i)) {
        	set.add(b/i);
        }
        if(l.contains(i)) {
        	set.add(i);
        }
    	 
        }
    } 
}
	int q=sc.nextInt();
	while(q-->0) {
		int x=sc.nextInt();
		int y=sc.nextInt();
		int max=0;
		if(set.ceiling(x)!=null &&set.floor(y)!=null) {
		 max=Math.max(set.ceiling(x), set.floor(y));	
		}
		else {
			max=-1;
		}
		if(max<x || max>y) {
		System.out.println(-1);
		continue;
		}
		else {
			System.out.println(max);
		}
		}
		
	
	}
static int ans;
	static int memo[];
	static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
	static long dp1(int a) {
	if(a==ans) {
		return 0;
	}	
	
	long d=Integer.MAX_VALUE;
	long b=Integer.MAX_VALUE;
	long c=Integer.MAX_VALUE;
		if(a%2==0&&a>ans) {
			d=1+dp1(a/2);
		}
		 if(a%3==0&&a>ans) {
			b=1+dp1(a/3);
		}
		 if(a%5==0&&a>ans) {
			c=1+dp1(a/5);
		}
		
		return Math.min(Math.min(d, b), c);
	}
	
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 boolean ready() throws IOException {return br.ready();}

	public double nextDouble() throws IOException 
	{
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if(x.charAt(0) == '-')
		{
			neg = true;
			start++;
		}
		for(int i = start; i < x.length(); i++)
			if(x.charAt(i) == '.')
			{
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			}
			else
			{
				sb.append(x.charAt(i));
				if(dec)
					f *= 10;
			}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg?-1:1);
	}


}
}