#include <bits/stdc++.h>

using namespace std;

vector<int> occ[1000005];
int lst[1000005];
vector<pair<int, int>> add[150005], que[150005];

const int INF = 1e9;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  auto getdivisor = [&](int x) {
    vector<int> v;
    for (int i = 1; i <= sqrt(x); i++) {
      if (x % i == 0) {
        v.push_back(i);
        if (i * i != x) {
          v.push_back(x / i);
        }
      }
    }
    return v;
  };
  for (int i = 0; i < n; i++) {
    auto divisor = getdivisor(a[i]);
    for (auto v : divisor) {
      occ[v].push_back(i);
    }
  }
  for (int i = 0; i < 1000005; i++) {
    occ[i].push_back(INF);
  }
  memset(lst, -1, sizeof lst);
  for (int i = 0; i < n; i++) {
    auto divisor = getdivisor(a[i]);
    for (auto v : divisor) {
      int pre = lst[v];
      if (pre == -1) {
        continue;
      }
      int bound = i + (i - pre);
      int nxt = *lower_bound(occ[v].begin(), occ[v].end(), bound);
      if (nxt == INF) {
        continue;
      }
      add[nxt].emplace_back(pre, v);
    }
    for (auto v : divisor) {
      lst[v] = i;
    }
  }

  vector<int> ans(q);
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    que[r].emplace_back(l, i);
  }

  vector<int> t(n * 2, 0);
  auto upd = [&](int i, int v) {
    i += n;
    while (i) {
      t[i] = max(t[i], v);
      i /= 2;
    }
  };
  auto query = [&](int l, int r) {
    int res = 0;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        res = max(res, t[l]);
        l++;
      }
      if (r & 1) {
        --r;
        res = max(res, t[r]);
      }
    }
    return res;
  };
  for (int i = 0; i < n; i++) {
    for (auto [l, v] : add[i]) {
      upd(l, v);
    }
    for (auto [l, id] : que[i]) {
      ans[id] = query(l, i);
    }
  }

  for (int i = 0; i < q; i++) {
    cout << ans[i] << "\n";
  }
}