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>
using namespace std;
bool comp(pair<long long, long long> a, pair<long long, long long> b) {
  return a.first < b.first;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long power(long long a, long long n) {
  long long res = 1;
  while (n > 0) {
    if (n % 2 != 0) {
      res *= a;
      n -= 1;
      res %= 1000000007;
    } else {
      a *= a;
      n /= 2;
      a %= 1000000007;
    }
  }
  return res;
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
      return false;
    }
  }
  return true;
}
void primeFactors(long long n) {
  while (n % 2 == 0) {
    cout << 2 << " ";
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      cout << i << " ";
      n = n / i;
    }
  }
  if (n > 2) {
    cout << n << " ";
  }
}
void printDivisors(long long n) {
  for (long long i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        cout << i << " ";
      else
        cout << i << " " << n / i << " ";
    }
  }
}
void BellmanFord(long long graph[][3], long long V, long long E,
                 long long src) {
  long long dis[V];
  for (long long i = 0; i < V; i++) dis[i] = INT_MAX;
  dis[src] = 0;
  for (long long i = 0; i < V - 1; i++) {
    for (long long j = 0; j < E; j++) {
      if (dis[graph[j][0]] + graph[j][2] < dis[graph[j][1]])
        dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2];
    }
  }
  bool flag = true;
  for (long long i = 0; i < E; i++) {
    long long x = graph[i][0], y = graph[i][1], weight = graph[i][2];
    if (dis[x] != INT_MAX && dis[x] + weight < dis[y]) {
      flag = false;
      break;
    }
  }
}
void topoSort(long long n, long long m, vector<vector<bool>> &e,
              vector<bool> &visited, long long x) {
  visited[x] = true;
  for (long long i = n - 1; i >= 0; i--) {
    if (e[x][i] and !visited[i]) {
      topoSort(n, m, e, visited, i);
    }
  }
  return;
}
void convertGraphToTree(long long x, vector<vector<long long>> &v,
                        vector<bool> &visited,
                        vector<vector<long long>> &newedges) {
  visited[x] = true;
  for (long long i = 0; i < v[x].size(); i++) {
    if (!visited[v[x][i]]) {
      newedges[x].push_back(v[x][i]);
      convertGraphToTree(v[x][i], v, visited, newedges);
    }
  }
  return;
}
long long subtreeCount(long long x, vector<vector<long long>> &v,
                       vector<bool> &visited, vector<long long> &count) {
  visited[x] = true;
  long long ans = 1;
  for (long long i = 0; i < v[x].size(); i++) {
    if (!visited[v[x][i]]) {
      ans += subtreeCount(v[x][i], v, visited, count);
    }
  }
  count[x] = ans;
  return ans;
}
void create_sparse_table(long long n, vector<long long> &v) {
  long long k = (long long)log2(n * 1.0);
  vector<vector<long long>> st(n + 1, vector<long long>(k + 1, 0));
  for (long long i = 0; i < n; i++) st[i][0] = v[i];
  for (long long j = 1; j <= k; j++) {
    for (long long i = 0; i + (1 << j) <= n; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
  return;
}
vector<long long> fact(200001, 1);
void preNCR() {
  for (long long i = 2; i < 200001; i++) {
    fact[i] = (fact[i - 1] * i) % 1000000007;
  }
  return;
}
long long ncr(long long n, long long r) {
  if (r > n) {
    return 0;
  }
  long long res = fact[n];
  res *= (power(fact[r], 1000000007 - 2) % 1000000007);
  res %= 1000000007;
  res *= (power(fact[n - r], 1000000007 - 2) % 1000000007);
  res %= 1000000007;
  return res;
}
void yes() { cout << "YES" << '\n'; }
void no() { cout << "NO" << '\n'; }
void helper(long long a, long long b, long long n,
            vector<pair<long long, long long>> &v) {
  set<long long> s;
  for (long long i = 1; i <= sqrt(a); i++) {
    if (a % i == 0) {
      if (a / i == i)
        s.insert(i);
      else
        s.insert(i);
      s.insert(a / i);
    }
  }
  vector<long long> ans;
  for (long long i = 1; i <= sqrt(b); i++) {
    if (b % i == 0) {
      if (b / i == i and s.find(i) != s.end())
        ans.push_back(i);
      else {
        if (s.find(i) != s.end()) ans.push_back(i);
        if (s.find(b / i) != s.end()) ans.push_back(b / i);
      }
    }
  }
  sort(ans.begin(), ans.end());
  vector<long long> final;
  for (long long i = 0; i < n; i++) {
    long long x = v[i].first, y = v[i].second;
    auto it = lower_bound(ans.begin(), ans.end(), y);
    if (it != ans.end() and (*it) == y)
      final.push_back(y);
    else {
      it--;
      if ((*it) >= x and (*it) <= y)
        final.push_back((*it));
      else
        final.push_back(-1);
    }
  }
  for (long long i = 0; i < final.size(); i++) {
    cout << final[i] << " ";
  }
  cout << '\n';
  return;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long a, b, n;
  cin >> a >> b >> n;
  vector<pair<long long, long long>> v(n, pair<long long, long long>());
  for (long long i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
  helper(a, b, n, v);
  return 0;
}