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>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;
inline bool isDigit(char c) { return '0' <= c && c <= '9'; }
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline bool isSquare(T x) {
  int y = sqrt(x + 0.5);
  return (y * y) == x;
}
template <class T1, class T2>
inline T1 gcd(T1 a, T2 b) {
  return b ? gcd(b, a % b) : a;
}
template <class T1, class T2>
inline T1 eqMin(T1& x, const T2& y) {
  if (T1(y) < x) return x = y;
  return x;
}
template <class T1, class T2>
inline T1 eqMax(T1& x, const T2& y) {
  if (T1(y) > x) return x = y;
  return x;
}
template <class T1, class T2>
inline T1 min(const T1& x, const T2& y) {
  return x < (T1)y ? x : (T1)y;
}
template <class T1, class T2>
inline T1 max(T1& x, const T2& y) {
  return x > (T1)y ? x : (T1)y;
}
template <typename T>
inline T getint() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') p = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * p;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << '{';
  bool was = false;
  for (const T& x : v) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << '}';
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  os << '[';
  bool was = false;
  for (const T& x : v) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << ']';
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  os << '[';
  bool was = false;
  for (const T& x : v) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << ']';
  return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& m) {
  os << '<';
  bool was = false;
  for (const auto& x : m) {
    if (was) os << ", ";
    was = true;
    os << x;
  }
  os << '>';
  return os;
}
template <size_t sz>
ostream& operator<<(ostream& os, const bitset<sz>& bit) {
  os << '/';
  for (int i = 0; i < sz; i++) os << bit[i];
  os << '\\';
  return os;
}
const double PI = acos(-1);
const double EPS = 1e-8;
const int INF = (int)2e9;
const long long LINF = (long long)2e18;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1;
int a, b;
map<int, int> s;
set<int> ss;
void fact(int a) {
  for (int i = 1; i * i <= a; i++) {
    if (a % i == 0) {
      s[i]++;
      if (a / i != i) s[a / i]++;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> a >> b;
  fact(a);
  fact(b);
  for (auto it : s) {
    if (it.second == 2) ss.insert(-it.first);
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    auto it = ss.lower_bound(-r);
    if (it == ss.end()) {
      cout << -1 << "\n";
      continue;
    }
    if (-(*it) < l) {
      cout << -1 << "\n";
      continue;
    }
    cout << -(*it) << "\n";
  }
}