﻿#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
#include <utility>
#include <iomanip>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <array>
#include <cassert>
#include <numeric>

#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define files freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)
#define sleep(_time) while ((double)clock() / (double)CLOCKS_PER_SEC < _time)

using namespace std;

const int MAX_N = 1e6;
const int MAX_LOG = 17;

int a[MAX_N];

vector<int> divisors[MAX_N];

void factor(int ind) {
    vector<int> ans;
    int x = a[ind];
    for (int i = 2; i * i <= a[ind]; ++i) {
        if (x % i == 0) {
            ans.push_back(i);
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x != 1) {
        ans.push_back(x);
    }
    divisors[ind] = move(ans);
}

bool used_divisors[MAX_N + 1];

bool check(int ind) {
    for (int x : divisors[ind]) {
        if (used_divisors[x]) {
            return false;
        }
    }
    return true;
}

void add(int ind) {
    for (int x : divisors[ind]) {
        used_divisors[x] = true;
    }
}

void del(int ind) {
    for (int x : divisors[ind]) {
        used_divisors[x] = false;
    }
}

int graph[MAX_N];
int dp[MAX_N][MAX_LOG];

int n;

void calc_dp() {
    for (int i = n - 1; i >= 0; --i) {
        if (graph[i] == n) {
            fill_n(dp[i], MAX_LOG, n);
        } else {
            dp[i][0] = graph[i];
            for (int j = 1; j < MAX_LOG; ++j) {
                if (dp[i][j - 1] == n) {
                    dp[i][j] = n;
                } else {
                    dp[i][j] = dp[dp[i][j - 1]][j - 1];
                }
            }
        }
    }
}

signed main() {
    fast;

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        factor(i);
    }
    int r = 0;
    for (int l = 0; l < n; ++l) {
        while ((r < n) && (check(r))) {
            add(r++);
        }
        graph[l] = r;
        del(l);
    }
    calc_dp();
    for (int _ = 0; _ < q; ++_) {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        int v = l;
        int ans = 0;
        for (int i = MAX_LOG - 1; i >= 0; --i) {
            if (dp[v][i] < r + 1) {
                v = dp[v][i];
                ans += 1 << i;
            }
        }
        ++ans;
        cout << ans << '\n';
    }

    return 0;
}