#include <bits/stdc++.h>
using namespace std;
    
int main (){

  #ifndef ONLINE_JUDGE
    freopen("SuhaibSawalha1","r",stdin);
  #endif

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  const int N = 1e5 + 1;
  int prime[N];
  iota(prime, prime + N, 0);
  for (int i = 2; i * i < N; ++i) {
  	if (prime[i] == i) {
  		for (int j = i * i; j < N; j += i) {
  			prime[j] = i;
  		}
  	}
  }
  int n, q;
  cin >> n >> q;
  int a[n];
  for (int i = 0; i < n; ++i) {
  	cin >> a[i];
  }
  int last[N] = {}, anc[n + 1][20];
  fill(anc[n], anc[n] + 20, n);
  for (int i = n - 1; ~i; --i) {
  	anc[i][0] = anc[i + 1][0];
  	while (a[i] != 1) {
  		int p = prime[a[i]];
  		if (last[p] && last[p] != i) {
  			anc[i][0] = min(anc[i][0], last[p]);
  		}
  		last[p] = i;
  		a[i] /= p;
  	}
  }
  for (int i = 1; i < 20; ++i) {
  	for (int j = 0; j < n; ++j) {
			anc[j][i] = anc[anc[j][i - 1]][i - 1];
  	}
  }
  while (q--) {
  	int l, r;
  	cin >> l >> r, --l;
  	int ans = 1;
  	for (int i = 19; ~i; --i) {
  		if (anc[l][i] < r) {
  			l = anc[l][i];
  			ans += 1 << i;
  		}
  	}
  	cout << ans << "\n";
  }

  return 0;
}
      	 						   	 	 	  	 	  		