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 CPP):

Solution:
#include <bits/stdc++.h>
const double pi = 3.14159265359;
const int OO = 1e9 + 7;
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
double sinA(double dig) { return sin(dig * pi / 180); }
double cosA(double dig) { return cos(dig * pi / 180); }
double tanA(double dig) {
  int we = dig;
  if (we == dig) {
    if (we % 90 == 0) {
      if ((we / 90) % 2 == 1)
        std::cout << "ERROR\n";
      else
        return 0;
    }
  }
  return tan(dig * pi / 180);
}
double secA(double dig) {
  int qw = cos(dig * pi / 180);
  if (qw == 0)
    std::cout << "ERROR\n";
  else
    return (1 / qw);
}
double cosecA(double dig) {
  int qw = sin(dig * pi / 180);
  if (qw == 0)
    std::cout << "ERROR\n";
  else
    return (1 / qw);
}
double cotA(double dig) {
  int qw = tan(dig * pi / 180);
  if (qw == 0)
    std::cout << "ERROR\n";
  else
    return (1 / qw);
}
template <class T>
inline std::istream& operator>>(std::istream& input, std::vector<T>& V) {
  for (auto& in : V) std::cin >> in;
  return input;
}
template <class T>
inline std::ostream& operator<<(std::ostream& out, std::vector<T>& V) {
  for (auto& h : V) out << h << " ";
  return out;
}
bool isPrime(long long num) {
  if (num < 0) num *= -1;
  if (num == 1 || num == 0)
    return false;
  else if (num == 2)
    return true;
  else {
    if (num % 2 == 0) {
      return false;
    } else
      for (int x = 3; x <= sqrt(num); x += 2) {
        if (num % x == 0) {
          return false;
        }
      }
    return true;
  }
}
double distAtoB(double A, double B) { return hypot(A, B); }
int gcd(int A, int B) {
  if (B == 0) return A;
  return gcd(B, A % B);
}
long long lcm(long long f, long long l) { return (f / gcd(f, l) * l); }
long long fact(long long number) {
  if (number < 0) number *= -1;
  if (number == 0) return 1;
  if (number == 1)
    return number;
  else
    return number * fact(number - 1);
}
long long fib(long long n) {
  auto sqrt_5 = std::sqrt(5);
  if (n == 0) return 0;
  if (n == 1) return 1;
  return static_cast<long long>(
      (std::pow(1 + sqrt_5, n) - std::pow(1 - sqrt_5, n)) /
      (std::pow(2, n) * sqrt_5));
}
long long cdiv(long long a, long long b) {
  return a / b + ((a ^ b) > 0 && a % b);
}
long long fdiv(long long a, long long b) {
  return a / b - ((a ^ b) < 0 && a % b);
}
long long rounding(long long a, long long b) { return (a + b / 2) / b; }
long long power(long long x, long long n) {
  if (n == 0) return 1;
  long long temp = power(x, n / 2);
  temp *= temp;
  if (n % 2) temp *= x;
  return temp;
}
long long powerMOD(long long x, long long n, long long m) {
  if (n == 0) return (1);
  long long temp = powerMOD(x, n / 2, m);
  temp = ((temp % m) * (temp % m)) % m;
  if (n % 2) temp = ((temp % m) * (x % m)) % m;
  return temp;
}
long long ETF(long long n) {
  long long ans = 1;
  for (long long x = 2; x * x <= n; x++) {
    if (n % x == 0) {
      long long count = 0;
      while (n % x == 0) {
        count++;
        n /= x;
      }
      ans *= (power(x, count - 1) * (x - 1));
    }
  }
  if (n != 1) ans *= (n - 1);
  return ans;
}
long long SUM(long long number) {
  long long ans = 0;
  while (number) {
    ans += number % 10;
    number /= 10;
  }
  return ans;
}
void generateNthrow(int N) {
  int prev = 1;
  std::cout << prev;
  for (int i = 1; i <= N; i++) {
    int curr = (prev * (N - i + 1)) / i;
    std::cout << ", " << curr;
    prev = curr;
  }
}
int logNM(int num1, int num2) {
  int counter = 0;
  while (num2) {
    num2 /= num1;
    counter++;
  }
  return counter;
}
void bits(int num) {
  if (num == 0 || num == 1) {
    std::cout << num;
    return;
  };
  bits(num / 2);
  std::cout << num % 2;
}
void run() {
  int num1, num2;
  std::cin >> num1 >> num2;
  int g = gcd(num1, num2);
  std::vector<int> v;
  for (int x = 1; x * x <= g; x++) {
    if (g % x == 0) {
      v.push_back(x);
      if (g / x != x) v.push_back(g / x);
    }
  }
  std::sort(v.begin(), v.end());
  ;
  int q;
  std::cin >> q;
  int l, r;
  bool f = 0;
  while (q--) {
    std::cin >> l >> r;
    f = 0;
    for (int x = v.size() - 1; x >= 0; x--) {
      if (v[x] >= l && v[x] <= r) {
        std::cout << v[x] << "\n";
        f = 1;
        break;
      }
    }
    std::cout << (!f ? "-1\n" : "");
  }
}
int main() {
  std::ios_base::sync_with_stdio(false), std::cout.tie(0), std::cin.tie(0);
  ;
  int t = 1;
  for (int CASE = 1; CASE <= t; CASE++) {
    run();
    std::cout << "\n";
  }
}