#include <bits/stdc++.h>
using namespace std;
const int N = 2e5, V = 51e5;
int n, q, f[N][16], bc[1 << 8 | 10];
int bt[V][8];
int pri[V / 10], pnum, npr[V];
inline void U(int &x, int y) { x < y ? x = y : 0; }
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 2; i < V; ++i)
    if (!npr[i]) {
      pri[++pnum] = i;
      for (int j = i + i; j < V; j += i) npr[j] = 1;
    }
  for (int i = 0; i < 1 << 8; ++i) bc[i] = bc[i >> 1] + (i & 1);
  for (int id = 1, x; id <= n; ++id) {
    scanf("%d", &x);
    int top = 0, sta[8];
    for (int i = 1; pri[i] * pri[i] <= x; ++i) {
      int nd = 0;
      while (x % pri[i] == 0) x /= pri[i], nd ^= 1;
      if (nd) sta[top++] = pri[i];
    }
    if (x > 1) sta[top++] = x;
    for (int i = 0; i < 1 << top; ++i) {
      int ans = 1;
      for (int j = 0; j < top; ++j)
        if (i >> j & 1) ans *= sta[j];
      for (int j = 0; j < 8; ++j) U(f[id][j + top - bc[i]], bt[ans][j]);
      bt[ans][top - bc[i]] = id;
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < 16; ++j) U(f[i][j], f[i][j - 1]);
    for (int j = 0; j < 16; ++j) U(f[i][j], f[i - 1][j]);
  }
  for (int id = 1, l, r; id <= q; ++id) {
    scanf("%d%d", &l, &r);
    for (int i = 0; i < 16; ++i)
      if (f[r][i] >= l) {
        printf("%d\n", i);
        break;
      }
  }
  return 0;
}
