#include<iostream>
#include<cstdio>
using namespace std;
int a[100005];
int f[1003][1003];
bool pr(int x){
    if(x==0||x==1) return 0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return 0;
    }
    return 1;
}
int sum(int l,int r){
    int ans=0;
    for(int i=l;i<=r;i++){
        ans|=a[i];
    }
    return ans;
}
int main(){
    freopen("Jelly.in","r",stdin);
    freopen("Jelly.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(pr(a[i])) f[i][i]=1;
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1]+pr(sum(l,r));
        }
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<f[l][r]<<endl;
    }
    return 0;
}