#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,tune=native")
template <typename T>
void print(T&& x) {
  cout << x << "\n";
}
template <typename T, typename... S>
void print(T&& x, S&&... y) {
  cout << x << ' ';
  print(y...);
}
const int Mod = 1000000007, Mod2 = 998244353;
const int MOD = Mod;
const int maxn = 200005;
int n, q, a[maxn], lpd[5100000], ans[1100000], cur, y, maxpos[15];
vector<int> pr;
vector<pair<int, int> > vec[5100000];
struct Query {
  int l, r, id;
} qry[1100000];
void hhhhauraorz() {
  lpd[0] = lpd[1] = 0;
  for (int i = (2); i < ((int)(5100000)); i++) {
    if (!lpd[i]) {
      lpd[i] = i;
      pr.push_back(i);
    }
    for (auto p : pr) {
      if (p * i >= 5100000) break;
      lpd[p * i] = p;
      if (i % p == 0) break;
    }
  }
  cin >> n >> q;
  for (int i = (0); i < ((int)(n)); i++) cin >> a[i];
  for (int i = (0); i < ((int)(q)); i++) cin >> qry[i].l >> qry[i].r;
  for (int i = (0); i < ((int)(q)); i++) qry[i].l--, qry[i].r--, qry[i].id = i;
  sort(qry, qry + q, [](Query& i, Query& j) { return i.r < j.r; });
  vector<int> vec1;
  int x;
  for (int i = (0); i < ((int)(15)); i++) maxpos[i] = -1;
  for (int i = (0); i < ((int)(n)); i++) {
    vec1.clear();
    for (int j = a[i]; j > 1; j /= lpd[j]) {
      if (vec1.empty() || vec1.back() != lpd[j])
        vec1.push_back(lpd[j]);
      else
        vec1.pop_back();
    }
    for (auto j : vec1) 826;
    826;
    for (int mask = (0); mask < ((int)((1ll << (((int)vec1.size())))));
         mask++) {
      x = 1;
      for (int j = (0); j < ((int)(((int)vec1.size()))); j++)
        if (mask & (1ll << (j))) x *= vec1[j];
      y = __builtin_popcountll(mask);
      for (auto& [c, d] : vec[x])
        maxpos[c + ((int)vec1.size()) - 2 * y] =
            max(maxpos[c + ((int)vec1.size()) - 2 * y], d);
      while (((int)vec[x].size()) && vec[x].back().first >= ((int)vec1.size()))
        vec[x].pop_back();
      vec[x].push_back({((int)vec1.size()), i});
    }
    while (cur < q && qry[cur].r == i) {
      for (int j = (14); j >= ((int)(0)); j--)
        if (maxpos[j] >= qry[cur].l) ans[qry[cur].id] = j;
      826;
      cur++;
    }
  }
  for (int i = (0); i < ((int)(q)); i++) print(ans[i]);
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t;
  t = 1;
  while (t--) hhhhauraorz();
  return 0;
}
