#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 1.5e5 + 9;
int n, m, B;

int ns[N];

struct {
  int l, r, i;
} q[N];

vi a[N];
vector<pair<int, int>> ad[N];

int L[N], R[N], id[N], s1[N], s2[N];

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  L (i, 1, n) {
    int x;
    cin >> x;
    for (int j = 1; j * j <= x; ++j) {
      if (x % j == 0) {
        a[j].eb(i);
        if (x / j > j) {
          a[x / j].eb(i);
        }
      }
    }
  }
  L (i, 1, n) {
    int k = sz(a[i]) - 1;
    R (j, sz(a[i]) - 1, 1) {
      while (k > j && a[i][k] - a[i][j] >= a[i][j] - a[i][j - 1]) {
        --k;
      }
      if (k < sz(a[i]) - 1) {
        ad[a[i][j - 1]].eb(a[i][k + 1], i);
      }
    }
  }
  L (i, 1, m) {
    cin >> q[i].l >> q[i].r;
    q[i].i = i;
  }
  sort(q + 1, q + m + 1, [] (auto a, auto b) {
    return a.l > b.l;
  });
  B = sqrt(n);
  for (int i = 1, l = 1, r; l <= n; ++i, l = r + 1) {
    r = min(l + B - 1, n);
    L[i] = l;
    R[i] = r;
    fill(id + l, id + r + 1, i);
  }
  int l = n;
  L (i, 1, m) {
    while (l >= q[i].l) {
      for (auto [x, y] : ad[l]) {
        s1[x] = max(s1[x], y);
        s2[id[x]] = max(s2[id[x]], y);
      }
      --l;
    }
    int z = id[q[i].r];
    R (k, z - 1, 1) {
      ns[q[i].i] = max(ns[q[i].i], s2[k]);
    }
    R (k, q[i].r, L[z]) {
      ns[q[i].i] = max(ns[q[i].i], s1[k]);
    }
  }
  L (i, 1, m) {
    cout << ns[i] << '\n';
  }
}
// I love WHQ!