#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 9;

int A[N], lp[N], up[N][50], last[N];

void Initialize () {
    for (int i = 1; i < N; i++)
        lp[i] = i;
    for (int i = 2; i * i < N; i++)
        if (lp[i] == i)
            for (int j = i * i; j < N; j += i)
                if (lp[j] == j) lp[j] = i;
    return;
}

vector <int> Factorize (int x) {
    vector <int> v;
    while (x > 1) {
        int u = lp[x];
        v.push_back (u);
        while (x % u == 0)
            x /= u;
    }
    return v;
}

void minimize (int& x, int y) {
    if (x > y) x = y;
    return;
}

int main () {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    Initialize ();
    for (int i = 1; i < N; i++)
        last[i] = n + 1;
    up[n + 1][0] = n + 1;
    for (int i = n; i >= 1; i--) {
        vector <int> primes = Factorize (A[i]);
        up[i][0] = up[i + 1][0];
        for (auto u: primes) {
            minimize (up[i][0], last[u]);
            last[u] = i;
        }
    }
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++)
            up[i][j] = up[up[i][j - 1]][j - 1];
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 1;
        for (int j = 20; j >= 0; j--) {
            if ((up[l][j] != 0) && (up[l][j] <= r))
                ans += (1 << j), l = up[l][j];
        }
        cout << ans << "\n";
    }
    return 0;
}
