#include <bits/stdc++.h>
using namespace std;
int n, q, l, r, cur = 1;
int a[194698], ans[5032117 / 4];
int ne_ans[18], ne_pos[10][5032117], sm[5032117];
bool p[5032117];
vector<pair<int, int> > v[194698];
void backt_track(int now, int tot, vector<int>& prs, int ps) {
  if (now == ((int)prs.size())) {
    for (int i = 0; i <= 8; i++)
      ne_ans[i + tot] = max(ne_ans[i + tot], ne_pos[i][cur]);
    ne_pos[tot][cur] = ps;
    return;
  }
  cur *= prs[now];
  backt_track(now + 1, tot, prs, ps);
  cur /= prs[now];
  backt_track(now + 1, tot + 1, prs, ps);
}
vector<int> process(int x) {
  vector<int> res;
  while (x > 1) {
    int tut = sm[x];
    int tot = 0;
    while (sm[x] == tut) x /= tut, tot++;
    if (tot & 1) res.push_back(tut);
  }
  return res;
}
void sieve() {
  for (int i = 2; i < 5032117; i++) {
    if (!p[i]) {
      for (int j = i; j < 5032117; j += i) {
        if (!sm[j]) sm[j] = i;
        p[j] = 1;
      }
    }
  }
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= q; i++) {
    scanf("%d %d", &l, &r);
    v[r].push_back({l, i});
  }
  sieve();
  for (int i = 1; i <= n; i++) {
    vector<int> prs = process(a[i]);
    backt_track(0, 0, prs, i);
    for (pair<int, int> Q : v[i]) {
      for (int j = 0; j <= 16; j++) {
        if (ne_ans[j] >= Q.first) {
          ans[Q.second] = j;
          break;
        }
      }
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}
