/*
Code by stringdp100005.
 
*/
 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
using i32 = int32_t;
using i64 = int64_t;
using ui32 = uint32_t;
using ui64 = uint64_t;
 
int t;
 
namespace strdp {
	const int N = 1e5, L = 20;
	int n, q, a[N + 5], lst[N + 5], r[N + 5];
	bool vis[N + 5];
	vector<int> divs[N + 5];
	struct ST {
		int st[L + 5][N + 5];
		void build() {
			for (int i = 1; i <= n; i++) st[0][i] = r[i];
			for (int i = 1; i <= L; i++) {
				for (int j = 1; j <= n; j++) {
					if (st[i - 1][j] <= n) st[i][j] = st[i - 1][st[i - 1][j]];
					else st[i][j] = n + 1;
				}
			}
		}
		int query(int l, int r) {
			int j = l;
			int res = 0;
			for (int i = L; i >= 0; i--) {
				if (st[i][j] <= r) {
					res += (1 << i);
					j = st[i][j];
				}
			}
			return res + 1;
		}
	} st;
	void main() {
		cin >> n >> q;
		for (int i = 1; i <= n; i++) cin >> a[i];
		for (int i = 1; i <= N; i++) lst[i] = r[i] = n + 1;
		for (int i = 2; i <= N; i++) {
			if (!vis[i]) {
				divs[i].push_back(i);
				for (int j = 2 * i; j <= N; j += i) {
					vis[j] = 1;
					divs[j].push_back(i);
				}
			}
		}
		for (int i = n; i >= 1; i--) {
			for (int j : divs[a[i]]) {
				r[i] = min(r[i], lst[j]);
				lst[j] = i;
			}
		}
		st.build();
		while (q--) {
			int l, r;
			cin >> l >> r;
			cout << st.query(l, r) << "\n";
		}
	}
}
 
 
i32 main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
	t = 1;
	// cin >> t;
 
	while (t--) strdp::main();
	return 0;
}