#include<bits/stdc++.h>
#define ll long long
#define N 1000001
using namespace std;
ll n,m,a[N],p[(1<<21)+1],ans[1001][1001],sor[1001][1001];
struct node{ll l,r;}ask[N];
ll read(){
    ll f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar();
        if(c=='-') f=-1;
    }
    while(c>='0'&&c<='9'){
        x=x*10+(c-'0');
        c=getchar();
    }
    return f*x;
}
void write(ll x){
    char c[31];
    ll cnt=0;
    while(x>0){
        c[++cnt]=x%10+'0';
        x/=10;
    }
    for(int i=cnt;i>0;i--) putchar(c[i]);
    putchar('\n');
    return ;
}
int main(){
    freopen("Jelly.in","r",stdin);
    freopen("Jelly.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++){
        ask[i].l=read();
        ask[i].r=read();
    }
    p[0]=p[1]=1;
    for(int i=2;i<=(1<<21);i++)
    if(p[i]==0) for(int j=2;i*j<=(1<<21);j++) p[i*j]=1;
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
        sor[i][j]=sor[i][j-1]|a[j];
        if(p[sor[i][j]]==0){
            for(int k=1;k<=i;k++)
            for(int l=j;l<=n;l++) ans[k][l]++;
        }
    }
    for(int i=1;i<=m;i++) write(ans[ask[i].l][ask[i].r]);
    return 0;
}