#include <bits/stdc++.h>

using namespace std;

vector<int> fact;
void factorise(int n){
	fact.clear();
	for (int i = 2; i*i <= n; ++i){
		if (n%i == 0){
			fact.push_back(i);	
		}
		while (n%i == 0){
			n /= i;
		}
	}
	if (n != 1){
		fact.push_back(n);	
	}
}

int main(){
	int n, q;
	cin >> n >> q;
	int a[n];
	for (int i = 0; i < n; ++i) cin >> a[i];
	
	vector<int> go(n, n);
	vector<int> v(100001, n);
	
	for (int i = n-1; i >= 0; --i){
		factorise(a[i]);
		for (int j : fact){
			go[i] = min(go[i], v[j]);
			v[j] = i;
		}
		if (i != n-1) go[i] = min(go[i], go[i+1]);
	}
	
	int lift[n][20];
	for (int i = n-1; i >= 0; --i){
		lift[i][0] = go[i];
		for (int j = 1; j < 20; ++j){
			if (lift[i][j-1] == n){
				lift[i][j] = n;	
			}
			else {
				lift[i][j] = lift[lift[i][j-1]][j-1];	
			}
		}
	}

	//for (int i = 0; i < n; ++i) cout << go[i] << ' ';
	cout << '\n';
	while (q--){
		int l, r;
		cin >> l >> r;
		--l; --r;
		int j = 0;
		
		for (int i = 19; i >= 0; --i){
			if (lift[l][i] <= r){
				l = lift[l][i];	
				j += (1 << i);
			}
		}
		cout << j+1 << '\n';
	}
	
	cout << '\n';
}