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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

											public class Solution1 implements Runnable
											{
												static final long MAX = 1000003L;
												static class InputReader
												{
													private InputStream stream;
													private byte[] buf = new byte[1024];
													private int curChar;
													private int numChars;
													private SpaceCharFilter filter;
													private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
											 
													public InputReader(InputStream stream)
													{
														this.stream = stream;
													}
													
													public int read()
													{
														if (numChars==-1) 
															throw new InputMismatchException();
														
														if (curChar >= numChars)
														{
															curChar = 0;
															try 
															{
																numChars = stream.read(buf);
															}
															catch (IOException e)
															{
																throw new InputMismatchException();
															}
															
															if(numChars <= 0)				
																return -1;
														}
														return buf[curChar++];
													}
												 
													public String nextLine()
													{
														String str = "";
											            try
											            {
											                str = br.readLine();
											            }
											            catch (IOException e)
											            {
											                e.printStackTrace();
											            }
											            return str;
													}
													public int nextInt()
													{
														int c = read();
														
														while(isSpaceChar(c)) 
															c = read();
														
														int sgn = 1;
														
														if (c == '-') 
														{
															sgn = -1;
															c = read();
														}
														
														int res = 0;
														do 
														{
															if(c<'0'||c>'9') 
																throw new InputMismatchException();
															res *= 10;
															res += c - '0';
															c = read();
														}
														while (!isSpaceChar(c)); 
														
														return res * sgn;
													}
													
													public long nextLong() 
													{
														int c = read();
														while (isSpaceChar(c))
															c = read();
														int sgn = 1;
														if (c == '-') 
														{
															sgn = -1;
															c = read();
														}
														long res = 0;
														
														do 
														{
															if (c < '0' || c > '9')
																throw new InputMismatchException();
															res *= 10;
															res += c - '0';
															c = read();
														}
														while (!isSpaceChar(c));
															return res * sgn;
													}
													
													public double nextDouble() 
													{
														int c = read();
														while (isSpaceChar(c))
															c = read();
														int sgn = 1;
														if (c == '-') 
														{
															sgn = -1;
															c = read();
														}
														double res = 0;
														while (!isSpaceChar(c) && c != '.') 
														{
															if (c == 'e' || c == 'E')
																return res * Math.pow(10, nextInt());
															if (c < '0' || c > '9')
																throw new InputMismatchException();
															res *= 10;
															res += c - '0';
															c = read();
														}
														if (c == '.') 
														{
															c = read();
															double m = 1;
															while (!isSpaceChar(c)) 
															{
																if (c == 'e' || c == 'E')
																	return res * Math.pow(10, nextInt());
																if (c < '0' || c > '9')
																	throw new InputMismatchException();
																m /= 10;
																res += (c - '0') * m;
																c = read();
															}
														}
														return res * sgn;
													}
													
													public String readString() 
													{
														int c = read();
														while (isSpaceChar(c))
															c = read();
														StringBuilder res = new StringBuilder();
														do 
														{
															res.appendCodePoint(c);
															c = read();
														} 
														while (!isSpaceChar(c));
														
														return res.toString();
													}
												 
													public boolean isSpaceChar(int c) 
													{
														if (filter != null)
															return filter.isSpaceChar(c);
														return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
													}
												 
													public String next() 
													{
														return readString();
													}
													
													public interface SpaceCharFilter 
													{
														public boolean isSpaceChar(int ch);
													}
												}
											 	
												public static void main(String args[]) throws Exception
												{
													new Thread(null, new Solution1(),"Solution",1<<26).start();
												}	
												public static int gcd(int a, int b)
											    {
											        if (a == 0)
											            return b;
											         
											        return gcd(b%a, a);
											    }
												int lcm(int a, int b)
												{
												    return (a*b)/gcd(a, b);
												}
												ArrayList<Integer> adj[];
												public void run() 
												{
													InputReader sc= new InputReader(System.in);
													PrintWriter w= new PrintWriter(System.out);
													int a=  sc.nextInt();
													int b=  sc.nextInt();
													TreeSet<Integer> tset = new TreeSet();
													for(int i = 1;i * i <= b;i++) {
														if(b % i == 0) {
															tset.add(i);
															tset.add(b/i);
														}
													}
													TreeSet<Integer> finale = new TreeSet();
													for(int i = 1;i * i <= a;i++) {
														if(a % i == 0) {
															if(tset.contains(a/i)) {
																finale.add(a/i);
															}
															if(tset.contains(i)) {
																finale.add(i);
															}
														}
													}
													int n = sc.nextInt();
													while(n-- > 0) {
														int x=  sc.nextInt();
														int y = sc.nextInt();
														Integer key1 = finale.floor(y);
														if(key1 != null && key1 >= x) {
															w.println(key1);
														}else {
															w.println("-1");
														}
													}
													w.close(); 
													
												}
												int fun(int n,int d,int e,int f) {
													int rem = -1;
													for(int i = 1;i <= 4000;i++) {
														if(d*i <= n && ((n - (d*i)) % e == 0 || (n - (d*i)) % f == 0)) {
															rem = i;
														}
													}
													return rem;
												}
												boolean[] visited;
												void bfs(int a) {
													Queue<Integer> q = new LinkedList();
													q.add(a);
													visited[a] = true;
													while(!q.isEmpty()) {
														int x = q.poll();
														Iterator<Integer> it = adj[x].iterator();
														while(it.hasNext()) {
															int temp = it.next();
															if(!visited[temp]) {
																visited[temp] = true;
																q.add(temp);
															}
														}
													}
												}
												
												long[][] segTree;
												long[][] arr;
												void build(int l,int r,int pos){
													if(l == r){
														segTree[pos][0] = arr[l][0];
														segTree[pos][1] = arr[l][1];
														return;
													}
													int mid = (l+r)/2;
													build(l, mid, 2*pos+1);
													build(mid+1, r, 2*pos+2);
													segTree[pos] = merge(segTree[2*pos+1],segTree[2*pos+2]);
												}
												long[] merge(long[] a,long[] b){
													long[] temp = new long[2];
													if(a[0] >= b[0]) {
														temp[0] = a[0];
														temp[1] = a[1];
													}else {
														temp[0] = b[0];
														temp[1] = b[1];
													}
													return temp;
												}
												long[] query(int l,int r,int start,int end,int pos){
													if(l > end || r < start || l > r){
														return new long[2];
													}
													if(l >= start && r <= end){
														return segTree[pos];
													}
													int mid = (l + r)/2;
													long[] p1 = query(l,mid, start, end, 2*pos+1);
													long[] p2 = query(mid+1, r, start, end, 2*pos+2);
													return merge(p1,p2);
												}
												long[][] multiply(long[][] a,long[][] b){
													long[][] temp = new long[3][3];
													for(int i = 0;i < 3;i++) {
														for(int j = 0;j < 3;j++) {
															for(int k = 0;k < 3;k++) {
																temp[i][j] = (temp[i][j] + (a[i][k] * b[k][j]) % MAX)%MAX;
															}
														}
													}
													return temp;
												}
												long pow(long[][] f,int val,long a,long b) {
													long[][] in = {{1,0,0},{0,1,0},{0,0,1}};
													while(val > 0) {
														if((val & 1) == 1) {
															in = multiply(in,f);
														}
														val = val/2;
														f = multiply(f, f);
													}
													return ((4*in[0][0])%MAX + (2*in[0][1])%MAX + in[0][2])%MAX;
												}
												   static long power(long x, long y,long p)
												    {
												        // Initialize result
												        long res = 1;     
												        
												        // Update x if it is more  
												        // than or equal to p
												        x = x % p; 
												     
												        while (y > 0)
												        {
												            // If y is odd, multiply x
												            // with result
												            if((y & 1)==1)
												                res = (res * x) % p;
												     
												            // y must be even now
												            // y = y / 2
												            y = y >> 1; 
												            x = (x * x) % p; 
												        }
												        return res;
												    }
												static class Pair implements Comparable<Pair>{
													int a;
													int b;
													long c;
													Pair(int a,int b,long c){
														this.a  =a;
														this.b = b;
														this.c = c;
													}
													Pair(){}	
													public boolean equals(Object o)
													{
														Pair p = (Pair)o;
														
														return true;
													}
													
													public int compareTo(Pair p){
														
														return Long.compare(this.c,p.c);
													}
												
												}
												
								}