#include <bits/stdc++.h>
using namespace std;
int n, q, a[200010], f[5100010][10], best[20];
int l[1100010], ans[1100010];
vector<int> p[200010], v[200010];
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    int t = a[i];
    for (int j = 2; j <= sqrt(t); j++) {
      int s = 0;
      while (t % j == 0) {
        s++;
        t /= j;
      }
      if (s & 1) {
        p[i].push_back(j);
      }
    }
    if (t > 1) {
      p[i].push_back(t);
    }
  }
  for (int i = 1; i <= q; i++) {
    int x;
    scanf("%d%d", &l[i], &x);
    v[x].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    int sz = p[i].size();
    for (int mask = 0; mask < (1 << sz); mask++) {
      int x = 1, y = 0;
      for (int j = 0; j < sz; j++) {
        if (mask & (1 << j)) {
          x *= p[i][j];
        } else {
          y++;
        }
      }
      for (int j = 0; j < 8 && j + y < 12; j++) {
        best[j + y] = max(best[j + y], f[x][j]);
      }
    }
    for (int j = 0; j < v[i].size(); j++) {
      int k = 0;
      while (best[k] < l[v[i][j]]) {
        k++;
      }
      ans[v[i][j]] = k;
    }
    for (int mask = 0; mask < (1 << sz); mask++) {
      int x = 1, y = 0;
      for (int j = 0; j < sz; j++) {
        if (mask & (1 << j)) {
          x *= p[i][j];
        } else {
          y++;
        }
      }
      f[x][y] = i;
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
