#include<bits/stdc++.h>
using namespace std;
bool p(int x){
    if(x==1||x==0){
        return false;
    }
    if(x==2){
        return true;
    }
    for(int i=2;i<x;i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}
int por(int x,int y){
    int xn[20],yn[20],i=0,nx=x,ny=y,sum=0;
    while(true){
        xn[i]=nx%2;
        nx=nx/2;
        yn[i]=ny%2;
        ny=ny/2;
        i++;
        if(nx==0&&ny==0){
            break;
        }
    }   
    for(int j=0;j<i;j++){
        if(xn[j]||yn[j]){
            sum+=pow(2,j);
        }
    } 
    return sum;
}
int n,m,a[100001],f[100001][100001];
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",&a[i]);
    }
    for(int i=1;i<=n;i++){
        int r=a[i];
        if(p(r)){
            f[i][i]=1;
        }
        for(int j=i+1;j<=n;j++){
            r=por(r,a[j]);
            if(p(r)){
                f[i][j]=1;
            }
        }
    }
    for(int i=1;i<=m;i++){
        int r,l,ans=0;
        scanf("%d%d",&r,&l);
        for(int j=r;j<=l;j++){
            for(int k=j;k<=l;k++){
                ans+=f[j][k];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}