#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
int n,m,a[N],mk[N][N],s[N][N];
bool check (int k) {
    if (k==0||k==1) return 0;
    for (int i=2;i<=sqrt(k);i++) {
        if (k%2==0) return 0;
    }
    return 1;
}
int main () {
    freopen("Jelly.in","r",stdin); 
    freopen("Jelly.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) {
        int sum=0;
        s[i][i]=0;
        for (int j=i;j<=n;j++) {
            sum|=a[j];
            s[i][j]=s[i][j-1];
            if (check(sum)) {
                mk[i][j]=1;
                s[i][j]++;
            }
        } 
    }
    while (m--) {
        int l,r;
        cin >> l >> r;
        ll ans=0;
        for (int i=l;i<=r;i++) {
            ans+=s[i][r];
        } 
        cout << ans <<endl;
    }
    return 0;
}