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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Set;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    CModifiedGCD solver = new CModifiedGCD();
    solver.solve(1, in, out);
    out.close();
  }

  static class CModifiedGCD {

    public void solve(int testNumber, InputReader in, PrintWriter out) {
      int a = in.nextInt();
      int b = in.nextInt();
      List<Integer> aDivisors = Ints.divisors(a);
      List<Integer> bDivisors = Ints.divisors(b);
      CountingMap<Integer> count = new CountingMap<>();
      for (int i : aDivisors) {
        count.increment(i);
      }
      for (int i : bDivisors) {
        count.increment(i);
      }
      List<Integer> common = new ArrayList<>(Math.max(aDivisors.size(), bDivisors.size()));
      for (Entry<Integer, Integer> pair : count.entrySet()) {
        if (pair.getValue() > 1) {
          common.add(pair.getKey());
        }
      }
      Collections.sort(common);
      int q = in.nextInt();
      while (q-- > 0) {
        int st = in.nextInt(), en = in.nextInt();
        int lo = 0, hi = common.size() - 1;
        int ans = -1;
        while (lo <= hi) {
          int mid = (lo + hi) >> 1;
          if (common.get(mid) <= en) {
            ans = mid;
            lo = mid + 1;
          } else {
            hi = mid - 1;
          }
        }
        if (ans == -1 || common.get(ans) < st) {
          out.println(-1);
        } else {
          out.println(common.get(ans));
        }
      }
    }

  }

  static class InputReader implements FastIO {

    private InputStream stream;
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static final int EOF = -1;
    private byte[] buf = new byte[DEFAULT_BUFFER_SIZE];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (this.numChars == EOF) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return EOF;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public int nextInt() {
      int c;
      for (c = this.read(); isSpaceChar(c); c = this.read()) {
      }

      byte sgn = 1;
      if (c == 45) {
        sgn = -1;
        c = this.read();
      }

      int res = 0;

      while (c >= 48 && c <= 57) {
        res *= 10;
        res += c - 48;
        c = this.read();
        if (isSpaceChar(c)) {
          return res * sgn;
        }
      }

      throw new InputMismatchException();
    }

    public static boolean isSpaceChar(int c) {
      return c == 32 || c == 10 || c == 13 || c == 9 || c == EOF;
    }

  }

  static interface FastIO {

  }

  static class Ints {

    public static List<Integer> divisors(int a) {
      List<Integer> result = new ArrayList<>();
      for (int i = 1; i * (long) i <= a; ++i) {
        if (a % i == 0) {
          result.add(i);
          if (a / i != i) {
            result.add(a / i);
          }
        }
      }
      return result;
    }

  }

  static class CountingMap<T> {

    private Map<T, Integer> map;

    public CountingMap() {
      map = new HashMap<>();
    }

    public CountingMap(int n) {
      map = new HashMap<>(n);
    }

    public CountingMap(CountingMap<T> map) {
      this.map = new HashMap<>(map.map);
    }

    public void increment(T key) {
      incrementBy(key, 1);
    }

    public void incrementBy(T key, Integer step) {
      map.put(key, map.getOrDefault(key, 0) + step);
    }

    public String toString() {
      return "CountingMap{" +
          "map=" + map +
          '}';
    }

    public Set<Entry<T, Integer>> entrySet() {
      return map.entrySet();
    }

  }
}