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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;


/**
 *
 * @author Kayali
 */
public class New {
      public static ArrayList<Integer> list = new ArrayList<>();
      public static int binarySearch(int low,int high)
	{
		int ans = -1;
		int start =0;
		int end = list.size()-1;
		while(start<=end)
		{
			int mid = (start+end)/2;
			int cur = list.get(mid);
			if(cur<low)
				start = mid+1;
			else if(cur>=low && cur<=high)
			{
				ans = cur;
				start = mid+1;
			}
			else
				end = mid-1;
		}
		
		return ans;
	}
public static TreeSet<Integer> getFactors(int x)
	{
		TreeSet<Integer> divisor = new TreeSet<>();
		for(int i=1;i*i<=x;i++)
		{
			if(x%i==0)
			{
				divisor.add(i);
				if(i!=(x/i))
					divisor.add(x/i);
			}
		}
		
		return divisor;
	}
	
    public static void main(String[] args) throws IOException {
    FastReader in = new FastReader();
       PrintWriter pw = new PrintWriter(System.out);
                int n1 = in.nextInt();
		int n2 = in.nextInt();
		TreeSet<Integer> ts1 = getFactors(n1);
		TreeSet<Integer> ts2 = getFactors(n2);
		for(int p: ts1) {
			if(ts2.contains(p))
				list.add(p);
		}
                
                int q = in.nextInt();
		while(q-->0) {
			int a = in.nextInt();
			int b = in.nextInt();
			b = Math.min(b, n2);
			
			int ans = binarySearch(a, b);
			pw.println(ans);
			
		}
                
                
                
       
     pw.flush();
     pw.close();
    
}
    

     static class FastReader {
 
        StringTokenizer st;
        BufferedReader br;
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public String next() throws IOException {
            if (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }
 
        public boolean hasNext() throws IOException {
            if (st != null && st.hasMoreTokens()) {
                return true;
            }
            String s = br.readLine();
            if (s == null || s.isEmpty()) {
                return false;
            }
            st = new StringTokenizer(s);
            return true;
        }
 
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
        public String nextLine() throws IOException {
            return br.readLine();
        }
    }
}