#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005, maxm = 5100005, N = 5100000;
int prime[maxm / 10], mn[maxn * 3], dv[maxm];
int lst[maxm][8], res[maxn * 5], n, Q, cnt, tn;
bool vis[maxm];
vector<pair<int, int> > vec[maxn], qr[maxn];
void update(int x, int w) {
  x += tn - 1;
  mn[x] = min(mn[x], w);
  while (x > 0) {
    x = (x - 1) >> 1;
    mn[x] = min(mn[x], w);
  }
}
int query(int a, int b, int l = 0, int r = tn, int k = 0) {
  if (a <= l && b >= r) return mn[k];
  if (a >= r || b <= l) return INT_MAX;
  int mid = (l + r) >> 1;
  return min(query(a, b, l, mid, k * 2 + 1), query(a, b, mid, r, k * 2 + 2));
}
int main() {
  scanf("%d%d", &n, &Q);
  for (int i = 2; i <= N; i++) {
    if (!vis[i]) {
      prime[++cnt] = i;
      dv[i] = i;
    }
    for (int j = 1; j <= cnt; j++) {
      int p = prime[j], q = i * p;
      if (q > N) break;
      vis[q] = true;
      dv[q] = p;
      if (i % p == 0) break;
    }
  }
  for (int i = 1; i <= n; i++) {
    int t, temp[20];
    memset(temp, 0, sizeof(temp));
    scanf("%d", &t);
    vector<int> d;
    while (t > 1) {
      int p = dv[t], c = 0;
      while (t % p == 0) t /= p, ++c;
      if (c & 1) d.push_back(p);
    }
    t = d.size();
    for (int j = 0; j < 1 << t; j++) {
      int mul = 1, c = 0;
      for (int k = 0; k < t; k++)
        if (j >> k & 1) mul *= d[k], ++c;
      for (int k = 0; k < 8; k++)
        if (lst[mul][k]) temp[t - c + k] = max(temp[t - c + k], lst[mul][k]);
      lst[mul][t - c] = i;
    }
    for (int j = 0; j < 20; j++)
      if (temp[j]) vec[i].push_back(pair<int, int>(j, temp[j]));
  }
  for (tn = 1; tn < n; tn <<= 1)
    ;
  memset(mn, 0x3f, sizeof(mn));
  for (int i = 1; i <= Q; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    qr[b].push_back(pair<int, int>(a, i));
  }
  for (int i = 1; i <= n; i++) {
    for (pair<int, int> p : vec[i]) update(p.second - 1, p.first);
    for (pair<int, int> p : qr[i]) res[p.second] = query(p.first - 1, i);
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", res[i]);
  return 0;
}
