#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5, MAXQ = 1 << 21, MAXM = 5100000;
int sito[MAXM];
void eratosten() {
  for (int i = (2); i < (MAXM); i++)
    if (!sito[i])
      for (int j = i; j < MAXM; j += i) sito[j] = i;
}
vector<int> Prosti(int x) {
  vector<int> R;
  for (; x > 1;) {
    int pr = sito[x], pot = 0;
    for (; sito[x] == pr; x /= sito[x], pot++)
      ;
    if (pot % 2) R.push_back(pr);
  }
  return R;
}
struct event {
  int r, val;
};
vector<event> Ev[MAXN];
int gdje[MAXM][8];
int p[MAXN];
void add_num(int pos) {
  vector<int> R = Prosti(p[pos]);
  int sz = (int)R.size();
  for (int msk = (0); msk < (1 << sz); msk++) {
    int umn = 1;
    for (int j = (0); j < (sz); j++)
      if (msk >> j & 1) umn *= R[j];
    gdje[umn][sz - __builtin_popcount(msk)] = pos;
  }
}
int n, brq;
void gen_events() {
  for (int i = (0); i < (MAXM); i++)
    for (int j = (0); j < (8); j++) gdje[i][j] = MAXN - 1;
  int mn[20];
  for (int i = n - 1; i >= 0; i--) {
    for (int j = (0); j < (20); j++) mn[j] = MAXN - 1;
    vector<int> R = Prosti(p[i]);
    int sz = (int)R.size();
    for (int msk = (0); msk < (1 << sz); msk++) {
      int umn = 1;
      for (int j = (0); j < (sz); j++)
        if (msk >> j & 1) umn *= R[j];
      for (int ost = (0); ost < (8); ost++) {
        int pos = gdje[umn][ost];
        int val = ost + sz - __builtin_popcount(msk);
        mn[val] = min(mn[val], pos);
      }
    }
    for (int j = (0); j < (20); j++) Ev[i].push_back({mn[j], j});
    add_num(i);
  }
}
int fen[MAXN];
vector<pair<int, int> > Q[MAXN];
int sol[MAXQ];
void upd(int pos, int val) {
  pos++;
  for (; pos < MAXN; pos += pos & -pos) fen[pos] = min(fen[pos], val);
}
int get(int pos) {
  pos++;
  int ret = MAXN;
  for (; pos; pos -= pos & -pos) ret = min(ret, fen[pos]);
  return ret;
}
void solve() {
  for (int i = (0); i < (MAXN); i++) fen[i] = MAXN;
  for (int i = n - 1; i >= 0; i--) {
    for (auto it : Ev[i]) upd(it.r, it.val);
    for (auto q : Q[i]) sol[q.second] = get(q.first);
  }
}
int main() {
  eratosten();
  scanf("%d%d", &n, &brq);
  for (int i = (0); i < (n); i++) scanf("%d", &p[i]);
  for (int i = (0); i < (brq); i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    r--;
    Q[l].push_back(pair<int, int>(r, i));
  }
  gen_events();
  solve();
  for (int i = (0); i < (brq); i++) printf("%d\n", sol[i]);
  return 0;
}
