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 long double pi = 3.141592654;
using namespace std;
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, -1, 1};
bool vis[1000000];
vector<int> vec;
const long long N = 1e5 + 5, inf = 2e9, mod = 1e10 + 7;
long long fact[1000006], inv[1000006];
vector<vector<int>> graph;
bool valid(int r, int c) { return (r >= 0 && c >= 0 && r < 8 && c < 8); }
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
void move1step(long long& a, long long& b, long long q) {
  long long c = a - b * q;
  a = b;
  b = c;
}
long long egcd(long long r0, long long r1, long long& x0, long long& y0) {
  x0 = 1;
  y0 = 0;
  long long x1 = 0, y1 = 1;
  while (r1) {
    long long q = r0 / r1;
    move1step(r0, r1, q);
    move1step(x0, x1, q);
    move1step(y0, y1, q);
  }
  return r0;
}
bool solve(long long a, long long b, long long c, long long& x, long long& y) {
  long long g = egcd(a, b, x, y);
  long long m = c / g;
  y *= m;
  x *= m;
  return (c % g == 0);
}
long long fp(unsigned long long base, unsigned long long exp) {
  if (exp == 0) return 1;
  unsigned long long ans = fp(base, exp / 2);
  ans = (ans * ans) % mod;
  if (exp % 2 != 0) ans = (ans * (base % mod)) % mod;
  return ans;
}
void calcFacAndInv(long long n) {
  fact[0] = inv[0] = 1;
  for (long long i = 1; i <= n; i++) {
    fact[i] = (i * fact[i - 1]) % mod;
    inv[i] = fp(fact[i], mod - 2);
  }
}
long long ncr(long long n, long long r) {
  return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}
long long npr(long long n, long long r) { return (fact[n] * inv[n - r]) % mod; }
vector<pair<long long, long long>> primeF(long long n) {
  vector<pair<long long, long long>> v;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      v.push_back({i, 0});
      while (n % i == 0) {
        v.back().second++;
        n /= i;
      }
    }
  }
  if (n > 1) {
    v.push_back({n, 1});
  }
  return v;
}
set<long long> st1, st2;
vector<pair<long long, long long>> v1, v2;
void getDivisors1(int ind = 0, long long res = 1) {
  if (ind == (int)v1.size()) {
    st1.insert(res);
    return;
  }
  for (long long i = 0; i <= v1[ind].second; i++) {
    getDivisors1(ind + 1, res);
    res = ((res % mod) * (v1[ind].first % mod)) % mod;
  }
}
void getDivisors2(int ind = 0, long long res = 1) {
  if (ind == (int)v2.size()) {
    st2.insert(res);
    return;
  }
  for (long long i = 0; i <= v2[ind].second; i++) {
    getDivisors2(ind + 1, res);
    res = ((res % mod) * (v2[ind].first % mod)) % mod;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long a, b;
  cin >> a >> b;
  v1 = primeF(a);
  v2 = primeF(b);
  sort(v1.rbegin(), v1.rend());
  sort(v2.rbegin(), v2.rend());
  getDivisors1();
  getDivisors2();
  int n;
  cin >> n;
  long long l, h, max;
  set<long long, long long>::reverse_iterator it;
  set<long long, long long>::reverse_iterator it1;
  vector<long long> v;
  for (it = st1.rbegin(); it != st1.rend(); it++) {
    for (it1 = st2.rbegin(); it1 != st2.rend(); it1++) {
      if (*it == *it1) {
        v.push_back(*it);
      }
    }
  }
  sort(v.rbegin(), v.rend());
  while (n--) {
    cin >> l >> h;
    max = -1;
    for (auto it : v) {
      if (it <= h && it >= l) {
        max = it;
        break;
      }
    }
    if (max != -1)
      cout << max << "\n";
    else
      cout << -1 << "\n";
  }
}