#include<iostream>
#include<cmath>
using namespace std;
int n,m;
int lis[100010];
int map[10010][10010];
bool isf(int x){
    if(x==1||x==0) return false;
    for(int i=2;i<=sqrt(x);i++) if(x%i==0) return false;
    return true;
}
int main(){
    freopen("Jelly.in","r",stdin);
    freopen("Jelly.out","w",stdout);
    
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&lis[i]);
    
    for(int i1=1;i1<=n;i1++){
        int p=lis[i1];
        for(int i2=i1;i2<=n;i2++){
            p=p|lis[i2];
            if(isf(p)) map[i1][i2]=1;
        }
    }
    
    while(m--){
        int l,r;scanf("%d%d",&l,&r);
        int ans=0;
        for(int i=l;i<=r;i++) for(int j=i;j<=r;j++) ans+=map[i][j];
        cout<<ans<<endl;
    }
    
    return 0;
}