#include <bits/stdc++.h>
using namespace std;
int x, primes[350588], p = 0;
vector<vector<int> > pfs(194598);
bool isprime[5032107 + 1];
unordered_map<int, int> rankd;
int dp[8][5032107], ans[15][194598], a[194598];
void getprimes() {
  for (int i = 2; i <= 5032107; i++) isprime[i] = true;
  for (int i = 2; i * i <= 5032107; i++) {
    if (isprime[i])
      for (int j = i + i; j <= 5032107; j += i) isprime[j] = false;
  }
  for (int i = 2; i <= 5032107; i++)
    if (isprime[i]) primes[p++] = i;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  getprimes();
  int n, x, i, j, cnt = 0, q;
  cin >> n >> q;
  for (i = 0; i < 8; i++)
    for (j = 0; j < 5032107; j++) dp[i][j] = -1;
  for (i = 0; i < 15; i++)
    for (j = 0; j < n; j++) ans[i][j] = -1;
  for (i = 0; i < n; i++) {
    cin >> x;
    for (j = 0; primes[j] * primes[j] <= x; j++) {
      if (x % primes[j] != 0) continue;
      while (x % (primes[j] * primes[j]) == 0) x /= (primes[j] * primes[j]);
      if (x % primes[j] == 0) {
        pfs[i].push_back(primes[j]);
        x /= primes[j];
      }
    }
    if (x > 1) pfs[i].push_back(x);
    a[i] = 1;
    for (auto it : pfs[i]) a[i] *= it;
    int jp = pfs[i].size();
    for (j = 0; j < (1 << jp); j++) {
      int curr = 1;
      for (int m = 0; m < jp; m++)
        if ((1 << m) & j) {
          curr *= pfs[i][m];
        }
      if (rankd.find(curr) != rankd.end()) {
        int sol = jp - __builtin_popcount(j), jj;
        for (jj = 0; jj < 8; jj++) {
          if (jj + sol > 14) break;
          ans[jj + sol][i] = max(ans[jj + sol][i], dp[jj][rankd[curr]]);
        }
      }
    }
    for (j = 0; j < (1 << jp); j++) {
      int curr = 1;
      for (int m = 0; m < jp; m++)
        if ((1 << m) & j) {
          curr *= pfs[i][m];
        }
      if (rankd.find(curr) == rankd.end()) {
        rankd.insert(make_pair(curr, cnt++));
      }
      int req = jp - __builtin_popcount(j);
      dp[req][rankd[curr]] = i;
    }
  }
  for (i = 1; i < n; i++) {
    for (j = 0; j < 15; j++) ans[j][i] = max(ans[j][i], ans[j][i - 1]);
  }
  while (q--) {
    int l, r, sol;
    cin >> l >> r;
    for (sol = 0; sol < 15; sol++)
      if (ans[sol][r - 1] >= l - 1) break;
    cout << sol << '\n';
  }
  return 0;
}
