#include <bits/stdc++.h>

const int N = 100010;

int n, q, a[N], pre[N], st[N], dp[N], f[N][20], g[N][20], p[N];

void rmq() {
	for (int i = 1; i <= n; i ++) g[i][0] = pre[i];
	for (int j = 1; j <= 19; j ++)
		for (int i = 1; i + (1 << j) - 1 <= n; i ++)
			g[i][j] = std::max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}

int que(int l, int r) {
	int k = p[r - l + 1];
	return std::max(g[l][k], g[r - (1 << k) + 1][k]);
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	for (int i = 2; i <= n; i ++) p[i] = p[i / 2] + 1; 
	for (int i = 1; i <= n; i ++) {
		int x = a[i], mx = 0;
		for (int j = 2; j * j <= x; j ++) {
			if (x % j == 0) {
				mx = std::max(mx, st[j]);
				st[j] = i;
				while (x % j == 0) x /= j;
			}
		}
		if (x > 1) {
			mx = std::max(mx, st[x]);
			st[x] = i;
		}
		pre[i] = mx;
	}
	rmq();
	for (int i = 1; i <= n; i ++) {
		int l = 1, r = i;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (que(mid, i) >= mid) l = mid + 1;
			else r = mid;
		}
		dp[i] = l;
	}
	for (int i = 1; i <= n; i ++) f[i][0] = dp[i] - 1;
	for (int j = 1; j <= 19; j ++) 
		for (int i = 1; i <= n; i ++) 
			if (f[i][j - 1]) f[i][j] = f[f[i][j - 1]][j - 1];
	while (q --) {
		int l, r;
		scanf("%d%d", &l, &r);
		int ans = 0;
		for (int i = 19; ~i; i --) {
			if (f[r][i] >= l) {
				r = f[r][i]; ans += (1 << i);
			}
		}
		printf("%d\n", ans + 1);
	}
	return 0;
}
