错的答案都是小1的，不知道为啥，心态崩了qaq

#include<bits/stdc++.h>
using namespace std;

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0);

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<int, PII> PPI;
typedef unsigned long long ULL;

const int INF = 0X3f3f3f3f, N = 1e5 + 10, MOD = 1e9 + 7;
const double eps = 1e-7, pi = acos(-1);

int a[N], pos[N]; // pos[i]质因子i出现的最小的下标 
int minp[N], primes[N];
int f[21][N]; 

void Init(int n) {
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if (!minp[i]) primes[cnt++] = i, minp[i] = i;
		for (int j = 0; primes[j] * i <= n; j++) {
			minp[primes[j] * i] = i;  
			if (i % primes[j] == 0) break;
		}
	}
}

void work() {
	int n, m;
	cin >> n >> m;
	
	rep (i, 1, n) cin >> a[i];
	
	rep (i, 0, 19) f[i][n + 1] = n + 1;
	
	rrep (i, n, 1) {
		f[0][i] = f[0][i + 1];
		int t = a[i];
		while (t - 1) {
			int mt = minp[t];
			if (pos[mt]) f[0][i] = min(f[0][i], pos[mt]);
			pos[mt] = i;
			while (t % mt == 0) t /= mt;
		}
	}
	
	rrep (i, n, 1) rep (j, 1, 19) f[j][i] = f[j - 1][f[j - 1][i]];
	
	while (m--) {
		int l, r, res = 1;
		cin >> l >> r;
		rrep (i, 19, 0) {
			if (f[i][l] <= r) {
				res += 1 << i;
				l = f[i][l];
			}
		}
		cout << res << endl;
	}
}

signed main() {
	IO
	Init(N - 1);

	int test = 1;

	while (test--) {
		work();
	}

	return 0;
}