#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;
const int Maxn = (1 << 20) + 10;

bool flag[Maxn];

int n;
int m;
int nums[N];
long long cal[N][N];
long long sums[N][N];

int main () {
    
    freopen ("Jelly.in", "r", stdin);
    freopen ("Jelly.out", "w", stdout);
    
    flag[0] = flag[1] = true;
    for (int i = 2; i < Maxn; i++) {
        if (!flag[i]) {
            for (int j = i + i; j < Maxn; j += i) {
                flag[j] = true;
            }
        }
    }
    
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &(nums[i]));
    }
    for (int i = 1; i <= n; i++) {
        int now = 0;
        for (int j = 1; j <= n; j++) {
            if (j >= i) {
                now |= nums[j];
            }
            
            cal[i][j] = cal[i][j - 1] + (!flag[now]);
            sums[i][j] = sums[i - 1][j] + cal[i][j];
        }
    }
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf ("%d%d", &l, &r);
        
        long long res = 0;
//        for (int j = l; j <= r; j++) {
//            res += cal[j][r];
//        }
        res = sums[r][r] - sums[l - 1][r];
        
        printf ("%lld\n", res);
    }
    
    return 0;
}