#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],vs[1050005],vv,v[1050005],ll,rr,s[1005][1005],as[1005][1005];
const int N=105;
int main(){
    freopen("Jelly.in","r",stdin);
    freopen("Jelly.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m,vs[1]=1;
    for(int i=2;i<=N;i++){
        if(!vs[i]) v[++vv]=i;
        for(int j=1;j<=vv&&i*v[j]<=N;j++){
            vs[i*v[j]]=1;
            if(i%v[j]==0) break;
        }
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int l=1;l<=n;l++){
        int ps=0;
        for(int r=l;r<=n;r++){
            ps|=a[r];
            s[l][r]=s[l][r-1]+(!vs[ps]);
        }
    }
    for(int r=1;r<=n;r++){
        for(int l=r;l>=0;l--){
            as[l][r]=as[l+1][r]+s[l][r];
        }
    }
    while(m--){
        cin>>ll>>rr;
        cout<<as[ll][rr]<<"\n";
    }
    return 0;
}