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.*;

public class C
{
   public static void main(String[] args)
   {
      new C(new FastScanner());
   }

   ArrayList<Integer> genPrimes(int N)
   {
      // Prime sieve
      boolean[] isPrime = new boolean[N+1];
      Arrays.fill(isPrime, true);
      isPrime[0] = false;
      isPrime[1] = false;
      for (int i=2; i<=N; i++)
         if (isPrime[i])
            for (long j=i*1L*i; j<=N; j+=i)
               isPrime[(int)j] = false;

      // Create an arraylist of primes
      ArrayList<Integer> primes = new ArrayList<Integer>();
      for (int i=0; i<=N; i++)
         if (isPrime[i])
            primes.add(i);
   
      return primes;
   }

   TreeSet<Node> genPrimeFactors(ArrayList<Integer> primes, int v)
   {
      TreeSet<Node> res = new TreeSet<Node>();
      for (int p : primes)
      {
         if (p > v)
            break;

         int cnt = 0;
         while ((v%p) == 0)
         {
            res.add(new Node(p, cnt++));
            v=v/p;
         }
      }

      return res;
   }

   int[] vs;
   int[] cnt;
   TreeSet<Integer> vals;

   void go(int i, int val)
   {
      if (i >= vs.length)
      {
         vals.add(val);
         return;
      }
      
      int u = 1;
      for (int j=0; j<=cnt[i]; j++)
      {
         go(i+1, val*u);
         u*=vs[i];
      }
   }

   public C(FastScanner in)
   {
      int a = in.nextInt();
      int b = in.nextInt();

      int MX = (int)(Math.sqrt(Math.max(a, b))+1);
      ArrayList<Integer> primes = genPrimes(MX);
      
      TreeSet<Node> fa = genPrimeFactors(primes, a);
      TreeSet<Node> fb = genPrimeFactors(primes, b);
      
      //System.out.println(fa); 
      //System.out.println(fb);
      fa.retainAll(fb);
      //System.out.println(fa); 

      TreeSet<Integer> cf = new TreeSet<Integer>();
      for (Node n : fa)
         cf.add(n.v);
      
      vs = new int[cf.size()];
      cnt = new int[cf.size()];
      vals = new TreeSet<Integer>();
      int pi = -1;
      for (Node n : fa)
      {
         if (n.cnt == 0)
         {
            pi++;
            vs[pi] = n.v;
         }
         cnt[pi]++;
      }

      go(0, 1);
      
      int nq = in.nextInt();
      while (nq-->0)
      {
         int lo = in.nextInt();
         int hi = in.nextInt();

         NavigableSet<Integer> ss = vals.subSet(lo, true, hi, true);
         if (ss.size() == 0)
            System.out.println("-1");
         else
            System.out.println(ss.last());
      }
   }
}

class Node implements Comparable<Node>
{
   int v;
   int cnt;

   public Node(int vv, int c)
   {
      v = vv;
      cnt = c;
   }

   public int compareTo(Node rhs)
   {
      if (v == rhs.v)
         return cnt-rhs.cnt;
      return v-rhs.v;
   }

   public String toString()
   {
      return v+" "+cnt;
   }
}

class FastScanner{
    int nextInt(){
        try{
            int c=System.in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextInt();
            int res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    long nextLong(){
        try{
            int c=System.in.read();
            if(c==-1) return -1;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return -1;
            }
            if(c=='-') return -nextLong();
            long res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    double nextDouble(){
        return Double.parseDouble(next());
    }
    
    String next(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(Character.isWhitespace(c))
                c=System.in.read();
            do{
                res.append((char)c);
            }while(!Character.isWhitespace(c=System.in.read()));
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
    
    String nextLine(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(c=='\r'||c=='\n')
                c=System.in.read();
            do{
                res.append((char)c);
                c=System.in.read();
            }while(c!='\r'&&c!='\n');
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
}