#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323
#define ll long long int
#define vi vector <int>
#define vl vector <ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
ll power(ll a, ll b) { //a^b
	ll res = 1;
	a = a % MOD;
	while (b > 0) {
		if (b & 1) {res = (res * a) % MOD; b--;}
		a = (a * a) % MOD;
		b >>= 1;
	}
	return res;
}

ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a % b);}

vl spf(100005, 1e17);

void sieve() {
	for (ll i = 2; i <= 100000; i++) {
		if (spf[i] == 1e17) {
			spf[i] = i;
			for (ll j = i * i; j <= 100000; j += i)
				spf[j] = i;
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	sieve();
	ll n, q;
	cin >> n >> q;
	vl a(n);
	for (auto &i : a)
		cin >> i;
	vl last(100001, n);
	vector <vl> nxt(n + 1, vl (31));
	for (ll i = 0; i < 31; i++)
		nxt[n][i] = n;
	for (ll i = n - 1; i >= 0; i--) {
		ll ma = n;
		ll z = a[i];
		while (z > 1) {
			ll d = spf[z];
			ma = min(ma, last[d]);
			while (z % d == 0)
				z = z / d;
			last[d] = i;
		}
		nxt[i][0] = ma;
		if (i + 1 < n) {
			nxt[i][0] = min(nxt[i][0], nxt[i + 1][0]);
		}
	}
	for (ll i = 1; i <= 30; i++) {
		for (ll j = n - 1; j >= 0; j--) {
			nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
		}
	}
	while (q--) {
		ll l, r;
		cin >> l >> r;
		l--;
		r--;
		ll cur = l;
		ll ans = 1;
		while (cur < r) {
			ll hav;
			for (ll i = 0; i < 31; i++) {
				if (nxt[cur][i] > r) {
					hav = i;
					break;
				}
			}
			if (hav == 0)
				break;
			ans += (1LL << (hav - 1));
			cur = nxt[cur][hav - 1];
		}
		cout << ans << "\n";
	}
}
