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.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

//http://codeforces.com/problemset/problem/75/C
public class ModifiedGCD {

	
static 	ArrayList<Integer> divisors;

	public static void main(String[] args) {

		Scanner s=new Scanner(System.in);
		int a ,b,n,l,h;
		a=s.nextInt();
		b=s.nextInt();
		n=s.nextInt();
		
		int g=gcd(a, b);
		get_divisors(g);
		while (n--!=0) {
			
			l=s.nextInt();
			h=s.nextInt();
			
			int v=upperBound( h);
			if (divisors.get(v)>=l && divisors.get(v)<=h) {
					System.out.println(divisors.get(v));

			}
			else
				System.out.println(-1);
			
			

				
			
		}
	}
	

	static int gcd(int m, int n)
	{
	    while(n != 0) {
	        int t = m % n;
	        m = n;
	        n = t;
		}

	    return m;
	}

	static void get_divisors(int g)
	{
		divisors=new ArrayList<>();
	  

	    for(int i = 1; i*i <= g; ++i) {
	        if(g % i == 0) {
	        	if (g/i==i) {
		            divisors.add(i);

				}
	        	else {
	            divisors.add(i);
	            divisors.add(g/i);
	        	}
	        }
	        
	    }


	   Collections.sort(divisors);
	}

	static int  upperBound(int key){
	    int s =0,e=divisors.size()-1;
	    int ans = -1;

	    while(s<=e){
	        int mid = (s+e)/2;

	        if(divisors.get(mid)==key){
		       return mid;
	        }
	        else if(divisors.get(mid)>key){
	            e = mid - 1;
	        }
	        else{
	            s = mid + 1;
	        }
	    }

	    return e;
	}


}