#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define db double
const int N = 5e5+10,M = 1e6+1e5;
const ll mod = 1e9+7;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c <= '9' && c >= '0';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}


int n,m;
int p[M+10],cnt,a[N];
bool v[M+10];
void pre(){
    v[0] = v[1] = 1;
    for(int i = 2;i <= M;i++){
        if(!v[i])p[++cnt] = i;
        for(int j = 1;j <= cnt && i <= M/p[j];j++){
            v[i * p[j]] = 1;
            if(i % p[j] == 0)break;
        }
    }
}
int s[1010][1010];
void work1(){
    for(int i = 1;i <= n;i++){
        int x = 0;
        for(int j = i;j <= n;j++){
            x |= a[j];
            if(!v[x])s[i][j]++;
            s[i][j] += s[i][j-1];
        }
    }
    for(int i = 1;i <= n;i++)
        for(int j = i;j <= n;j++)s[i][j] += s[i-1][j];
    for(int i = 1;i <= m;i++){
        int l = read(),r = read();
        printf("%d\n",s[r][r] - s[l-1][r]);
    }
}
void solve(){
    pre();
    n = read(),m = read();
    for(int i = 1;i <= n;i++)a[i] = read();
    if(n <= 1000){
        work1();
        return;
    }
    
} 
int main(){
    freopen("Jelly.in","r",stdin);
    freopen("Jelly.out","w",stdout);
    int t = 1;
    while(t--)solve();
    
    return 0;
    
}