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;
using ll = long long int;
using dd = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
ll INFLL = (ll)2e18, MOD = 1e9 + 7;
const int INF = 0x6f6f6f6f;
vector<vector<ll>> adj;
vector<int> vis;
int dx8[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[] = {1, 1, 0, -1, -1, -1, 0, 1},
    dx4[] = {0, 1, 0, -1}, dy4[] = {1, 0, -1, 0};
inline ll mexp(ll x, ll n, ll m) {
  ll res = 1;
  while (n) {
    if (n & 1) res = (res * x) % m;
    n >>= 1;
    x = ((x % m) * (x % m)) % m;
  }
  return res;
}
inline bool ispow2(ll x) { return x && (!(x & (x - 1))); }
inline ll gcd(ll x, ll y) {
  pll p{x, y};
  while (p.second) p = {p.second, p.first % p.second};
  return p.first;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed;
  cerr << fixed;
  cout << setprecision(10);
  cerr << setprecision(3);
  mt19937 genr(chrono::high_resolution_clock::now().time_since_epoch().count());
  set<int> div;
  int a, b;
  cin >> a >> b;
  if (a > b) swap(a, b);
  for (int d = 1; d * d <= a; ++d) {
    if (a % d == 0 && b % d == 0) div.insert(d);
    int other = a / d;
    if (a % other == 0 && b % other == 0) div.insert(other);
  }
  for (auto& e : div) cerr << e << ' ';
  cout << '\n';
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int l, r;
    cin >> l >> r;
    auto it = div.upper_bound(r);
    --it;
    if (*it >= l)
      cout << *it << '\n';
    else
      cout << -1 << '\n';
  }
  return 0;
}