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;
long long int Mmax(long long int a, long long int b) {
  if (a > b) return a;
  return b;
}
long long int Mmin(long long int a, long long int b) {
  if (a < b) return a;
  return b;
}
long long int nod(long long int a, long long int b) {
  while (a && b) {
    if (a > b)
      a %= b;
    else
      b %= a;
  }
  return Mmax(a, b);
}
long long int nok(long long int a, long long int b) {
  return a * b / nod(a, b);
}
bool IsPrime(long long int x) {
  if (x < 2) return false;
  long long int X = sqrt(x), i;
  for (i = 2; i <= X; i++)
    if (x % i == 0) return false;
  return true;
}
void hanoi(int n, int A, int C, int B) {
  if (n == 1) {
    cout << n << " " << A << " " << C << endl;
  } else {
    hanoi(n - 1, A, B, C);
    cout << n << " " << A << " " << C << endl;
    hanoi(n - 1, B, C, A);
  }
}
string pr2(string a, int d) {
  if (d == 0) return "0";
  string b;
  long long int sz = a.size(), i, prenos = 0;
  for (i = 0; i < sz; i++) {
    b[i] = a[i];
  }
  for (i = sz - 1; i > -1; i--) {
    a[i] = ((b[i] - '0') * d + prenos) % 10 + '0';
    prenos = ((b[i] - '0') * d + prenos) / 10;
  }
  if (prenos) a = char(prenos + '0') + a;
  return a;
}
string sum(string a, string b) {
  bool carry = false;
  long long int i, sz1, sz2, maxsz, minsz;
  string c, d;
  sz1 = a.size();
  sz2 = b.size();
  maxsz = max(sz1, sz2);
  minsz = min(sz1, sz2);
  while (sz1 < maxsz) {
    sz1++;
    a = '0' + a;
  }
  while (sz2 < maxsz) {
    sz2++;
    b = '0' + b;
  }
  for (i = maxsz - 1; i > -1; i--) {
    d = char((a[i] + b[i] - 96 + carry) % 10 + 48) + d;
    if (a[i] + b[i] - 96 + carry > 9)
      carry = true;
    else
      carry = false;
  }
  if (carry == true) d = char('1') + d;
  return d;
}
string pr(string a, string b) {
  string res = "0", p, p2;
  int sz = a.size(), x = 0;
  for (sz = a.size(); sz > 0; sz--, x++) {
    int d = a[sz - 1] - '0';
    a = a.erase(sz - 1, 1);
    p2 = pr2(b, d);
    p2 += p;
    res = sum(res, p2);
    p += "0";
  }
  return res;
}
bool vesokosna(long long int x) {
  return (x % 4 == 0 && x % 100 || x % 400 == 0);
}
long long int reverse(long long int x) {
  long long int mirror = 0;
  while (x) {
    mirror = mirror * 10 + x % 10;
    x /= 10;
  }
  return mirror;
}
long long int ost(string x, long long int k) {
  long long int num = 0, i, sz = x.size();
  for (i = 0; i < sz; i++) {
    num = num * 10;
    num += x[i] - '0';
    num %= k;
  }
  return num;
}
vector<long long> d;
int main() {
  long long a, b;
  cin >> a >> b;
  long long nd = nod(a, b), i, sq = sqrt(nd);
  for (i = 1; i <= sq; i++) {
    if (nd % i == 0) {
      d.push_back(i);
      if (i * i != nd) d.push_back(nd / i);
    }
  }
  sort(d.begin(), d.end());
  long long sz = d.size();
  long long m, j;
  cin >> m;
  for (j = 0; j < m; j++) {
    long long low, high, i, ans = -1;
    cin >> low >> high;
    for (i = 0; i < sz; i++) {
      if (d[i] >= low && d[i] <= high) ans = d[i];
    }
    cout << ans << endl;
  }
  return 0;
}