#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 1e5 + 1;


void test_case()
{
    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> v(n), primes(N, -1), right(n);
    for (int i = 0; i < n; i++) scanf("%d", &v[i]);
    vector<vector<int>> p(N);
    for (int i = 2; i < N; i++)
    {
        if (p[i].empty())
        {
            for (int j = i; j < N; j += i) p[j].push_back(i);
        }
    }
    for (int i = n - 1; i >= 0; i--)
    {
        int id = 1e9;
        for (int& d : p[v[i]])
        {
            if (primes[d] != -1) id = min(id, primes[d]);
            primes[d] = i;
        }
        if (i == n - 1) right[i] = n;
        else right[i] = min(right[i + 1], id);
    }
    vector<vector<int>> up(n + 5, vector<int>(20, 1e9));
    for (int i = n - 1; i >= 0; i--)
    {
        up[i][0] = right[i];
        for (int j = 1; j < 20; j++) up[i][j] = min(up[up[i][j - 1]][j - 1], n);
    }
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l--;
        r--;
        int c = 0;
        for (int i = 19; i >= 0; i--)
        {
            if (up[l][i] <= r)
            {
                c += (1 << i);
                l = up[l][i];
            }
        }
        printf("%d\n", c + 1);
    }
}

int main()
{
    /*int tc;
    scanf("%d", &tc);
    while (tc--)*/
        test_case();
    return 0;
}