#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>

using namespace std;

const int A = 100005;
int arr[A];
int last[A];
int pre[A];
int dp[21][A];

int main() {
    int n, m, x;
    scanf("%d%d", &n, &m);
    for(auto i=1;i<=n;i++) {
        scanf("%d", &x);
        pre[i] = pre[i-1];
        for(auto j=2; j*j<=x; j++) {
            if (x % j == 0) {
                while(x % j == 0) {
                    x /= j;
                }
                pre[i] = max(pre[i], last[j]);
                last[j] = i;
            }
        }
        if (x != 1) {
            pre[i] = max(pre[i], last[x]);
            last[x] = i;
        }
        dp[0][i] = pre[i];
    }
    for(auto k=1; k<=20; k++) {
        for(auto i=1; i<=n; i++) {
            dp[k][i] = dp[k-1][dp[k-1][i]];
        }
    }
    int a, b;
    for(auto i=0;i<m;i++) {
        scanf("%d%d", &a, &b);
        int ans = 0;
        for(auto j=20;j>=0;j--) {
            if (dp[j][b]>=a) {
                ans += (1<<j);
                b = dp[j][b];
            }
        }
        printf("%d\n", ans+1);

    }
    //printf("%lf\n", 1000.0*(clock() - start)/CLOCKS_PER_SEC);
    return 0;
}