#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int a[N];
int b[N];
int f[N][20];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= 100000; ++i) {
        b[i] = n + 1;
    }
    f[n + 1][0] = n + 1;
    for (int i = n; i; --i) {
        int x = a[i];
        f[i][0] = f[i + 1][0];
        for (int j = 2; j * j <= x; ++j) {
            if (x % j == 0) {
                f[i][0] = min(f[i][0], b[j]);
                b[j] = i;
                for (; x % j == 0; x /= j)
                    ;
            }
        }
        if (x > 1) {
            f[i][0] = min(f[i][0], b[x]);
            b[x] = i;
        }
    }
    for (int i = 1; i <= 17; ++i) {
        for (int j = 1; j <= n + 1; ++j) {
            f[j][i] = f[f[j][i - 1]][i - 1];
        }
    }
/*    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 4; ++j) {
            cout << i << ' ' << j << ' ' << f[i][j] << endl;
        }
    }*/
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 1;
        for (int i = 17; i >= 0; --i) {
            if (f[l][i] <= r) {
                ans += 1 << i;
                l = f[l][i];
            }
        }
        cout << ans << endl;
    }
}