#include<bits/stdc++.h>
#define ll long long
#define ri register int
#define lowbit(x) x&(-x)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
const int p = 1e9+7;
const int maxn = 4e5+10;
int n, m, t, q;
int a[maxn], vis[maxn], go[maxn], two;
int dp[maxn][30];
void divide(int x, int k){
	int t = sqrt(x);
	for(int i = 2;i <= t;i ++){
		if(x%i == 0){
			vis[i] += k;
			if(vis[i] == 1 && k == -1) two --;
			else if(vis[i] >= 2) two ++;
			while(x%i == 0) x /= i;
		}
	}
	if(x > 1){
		vis[x] += k;
		if(vis[x] == 1 && k == -1) two --;
		else if(vis[x] >= 2) two ++;
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i = 1;i <= n;i ++)
		scanf("%d",&a[i]);
	int l = 1, r = 0;
	while(r < n){
		r ++;
		divide(a[r], 1);
		if(two){
			go[l] = r;
			while(two){
				divide(a[l], -1);
				l ++;
				go[l] = r;
			}
		}
	}
	for(int i = l;i <= n+1;i ++)
		go[i] = n+1;
	for(int i = 1;i <= n;i ++){
		dp[i][0] = go[i];
	}
	for(int j = 1;j <= 20;j ++)
		for(int i = 1;i <= n+1;i ++){
			if(dp[dp[i][j-1]][j-1])
				dp[i][j] = dp[dp[i][j-1]][j-1];
			else dp[i][j] = n+1;
		}
	for(int i = 1;i <= q;i ++){
		int l, r;
		ll ans = 0;
		scanf("%d%d",&l,&r);
		for(int j = 20;j >= 0;j --){
			//cout << l << " " << j << " " << dp[l][j] << endl;
			if(dp[l][j] <= r){
				l = dp[l][j];
				ans += 1ll<<j;
			}
		}
		printf("%lld\n",ans+1);
	}
	return 0;
}