#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a[N];
struct Tree{
    int o,L,R,lc,rc;
}f[2*N];
int rt=0,tot=0;
int build(int l,int r)
{
    int c=++tot;
    f[c].L=l,f[c].R=r;
    if(l==r){
        f[c].o=a[l];
        return c;
    }
    int m=(l+r)/2;
    int lc=f[c].lc=build(l,m);
    int rc=f[c].rc=build(m+1,r);
    f[c].o=f[lc].o|f[rc].o;
    return c;
}
int query(int c,int l,int r)
{
    if(l<=f[c].L&&f[c].R<=r) return f[c].o;
    int M=(f[c].L+f[c].R)/2;
    int lc=f[c].lc,rc=f[c].rc;
    int oi=0;
    if(l<=M) oi|=query(lc,l,r);
    if(M<r) oi|=query(rc,l,r);
    return oi;
}
bool prime(int x)
{
    if(x<2) return false;
    for(int i=2;i*i<=x;i++) if(x%i==0) return false;
    return true;
}
signed main()
{
    freopen("Jelly.in","r",stdin);
    freopen("Jelly.out","w",stdout);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    rt=build(1,n);
    while(m--)
    {
        int L,R,ans=0;
        cin>>L>>R;
        for(int len=1;len<=R-L+1;len++){
            for(int l=L;l+len-1<=R;l++){
                int r=l+len-1;
                int t=query(rt,l,r);
                //cout<<l<<' '<<r<<' '<<len<<' '<<t<<' '<<prime(t)<<endl;
                if(prime(t)) ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}