#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3", "omit-frame-pointer","inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,fma,popcnt,abm,mmx,avx,avx2")

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

/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______
 * |\  \|\  \  |\  ___ \  |\  ___ \
 * \ \  \/  /|_\ \   __/| \ \   __/|
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
//const long long mod = 1000000007;
const long long mod = 998244353;
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 100010;
const int lg = 23;

int mnp[mxN];

void sieve() {
	mnp[0] = mnp[1] = 1;
	for (int i = 2; i < mxN; i++)
		if (!mnp[i]) for (int j = i; j < mxN; j += i)
			mnp[j] = i;
}

int main(int argc, char *argv[]) {
#ifdef ONLINE_JUDGE
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif

	srand(time(NULL));
	cout << fixed << setprecision(9);

	sieve();

	int t = 1;
//	int Case = 1;
//	cin >> t;
//	t = 10000;
	while (t--) {
		int n, q;
		cin >> n >> q;
		vector<int> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];
		vector<int> nxt(n);
		vector<int> cur(mxN, n);
		for (int i = n - 1; i >= 0; i--) {
			int to = n;
			int x = a[i];
			while (x > 1) {
				int dv = mnp[x];
				to = min(to, cur[dv]);
				cur[dv] = i;
				while (x % dv == 0)
					x /= dv;
			}
			nxt[i] = to;
		}
		vector<int> rb(n + 1, n);
		for (int i = n - 1; i >= 0; i--) {
			rb[i] = min(rb[i + 1], nxt[i]);
		}
		vector<vector<int>> dp(n + 1, vector<int>(lg));
		for (int j = 0; j < lg; j++)
			dp[n][j] = n;
		for (int i = n - 1; i >= 0; i--) {
			dp[i][0] = rb[i];
			for (int j = 1; j < lg; j++)
				dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
		for (int i = 0, l, r; i < q; i++) {
			cin >> l >> r;
			l--, r--;
			int res = 0, cur = l;
			for (int j = lg - 1; j >= 0; j--) {
				while (dp[cur][j] <= r)
					cur = dp[cur][j], res += (1 << j);
			}
			res++;
			cout << res << '\n';
		}
	}
	return 0;
}

/* stuff you should look for:
 * overflow, array bounds
 * special cases (n=1?)
 * clear arrays
 * DON'T STICK TO ONE APPROACH
 * solve simpler or different variation
 * Solve DP using graph ( \_(-_-)_/ )
 */
