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:
//189301019.akshay
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer; 
import java.util.Collections;
public class E 
{ 
    public static void main(String[] args) 
	{ 
		FastReader sc=new FastReader(); 
		StringBuffer ans=new StringBuffer();
		int test=1;
		
		
		while(test-->0)
		{
			long a=sc.nextLong(),b=sc.nextLong();
			
			long gcd = findGCD(a,b);
			long gcdd = gcd;
//			HashMap<Long,Integer> map = new HashMap<>();
//			for(long i=2;i*i<=gcd;i++) {
//				while(gcd%i == 0) {
//					if(map.containsKey(i)) {
//						map.put(i,map.get(i)+1);
//					}
//					else {
//						map.put(i, 1);
//					}
//					gcd= gcd/i;
//				}
//			}
//			if(gcd>1) {
//				
//			}
			ArrayList<Long> factors = new ArrayList<>();
			for(long i=1;i*i<=gcdd;i++) {
				if(gcdd%i == 0) {
					long aa = gcdd/i;
					long bb = gcdd/aa;
					factors.add(aa);
					if(aa !=bb)
						factors.add(bb);
				}
			}
			
			Collections.sort(factors);
			int len = factors.size();
			int n=sc.nextInt();
			while(n-->0) {
				long l = sc.nextLong(),r=sc.nextLong();
				
				int low = 0;
				int high = len-1;
				long possible = -1;
				while(low<=high) {
					int mid = low+(high-low)/2;
					
					if(factors.get(mid)<=r) {
						possible = factors.get(mid);
						low=mid+1;
					}
					else {
						high=mid-1;
					}
				}
				
				if(possible != -1 && possible<l) {
					possible = -1;
				}
				ans.append(possible+"\n");
				
				
				 
			}
			
			
		
		}
		
	    System.out.print(ans);
	} 
    
    static long findGCD(long a,long b) {
    	if(b == 0)
    		return a;
    	return findGCD(b,a%b);
    }
    
    static final Random random=new Random();
    
	static void ruffleSort(int[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	static void ruffleSort(long[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n);
			long temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	static class FastReader 
	{ 
		BufferedReader br; 
		StringTokenizer st; 

		public FastReader() 
		{ 
			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; 
		} 
	} 


}