#include<iostream>
using namespace std;

const int N = 1005;
int n, m;
int a[N];
int ans[N][N];
int ok[N][N];
bool check(int x){
    if(x == 0 || x == 1) return false;
    int s = 2;
    for(;s * s <= x;s ++){
        if(x % s == 0) return false;
    }
    return true;
}

int main(){
    freopen("Jelly.in", "r", stdin);
    freopen("Jelly.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    
    cin >> n >> m;
    
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }
    
    for(int i = 1;i <= n;i ++){
        int kksc03 = 0;
        for(int j = i;j <= n;j ++){
            kksc03 |= a[j];
            ok[i][j] = ok[i][j - 1] + check(kksc03); 
        }
    }
    
    for(int j = 1;j <= n;j ++){
        for(int i = j;i >= 1;i --){
            ans[i][j] = ans[i + 1][j] + ok[i][j];
        }
    }
    
    while(m --){
        int l, r;
        cin >> l >> r;
        cout << ans[l][r] << '\n';
    }
    return 0;
}