#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <bitset>
#include <unordered_map>

using namespace std;
#define int long long


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<vector<int>> p(n);
    for (int i = 0; i < n; ++i) {
        int p1 = 2, a1 = a[i];
        while (a1 > 1 && p1 * p1 <= a1){
            if (a1 % p1 == 0){
                while (a1 % p1 == 0) a1 /= p1;
                p[i].push_back(p1);
            }
            p1++;
        }
        if (a1 > 1) p[i].push_back(a1);
    }
    vector<int> b(n);
    int t = 0;
    vector<int> used(1e5 + 1);
    for (int i = 0; i < n; ++i) {
        bool check = false;
        while (!check && t + i < n) {
            for (int j = 0; j < p[i + t].size(); ++j) {
                if (used[p[i + t][j]]){
                    check = true;
                    break;
                }
            }
            if (!check){
                for (int j = 0; j < p[i + t].size(); ++j) {
                    used[p[i + t][j]]++;
                }
                t++;
            }
        }
        b[i] = t;
        t--;
        for (int j = 0; j < p[i].size(); ++j) {
            used[p[i][j]]--;
        }
    }
    vector<vector<int>> dp(n, vector<int> (20, n));
    for (int i = n - 1; i >= 0; --i) {
        dp[i][0] = i + b[i];
        for (int j = 1; j < 20; ++j) {
            if (dp[i][j - 1] != n) dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        int ans = 0;
        for (int j = 19; j >= 0; --j) {
            if (dp[l][j] <= r){
                ans += (1 << j);
                l = dp[l][j];
            }
        }
        cout << ans + 1 << endl;
    }
}