#include <bits/stdc++.h>
                
using namespace std;

int n, m;
int a[100005];
int f[1005][1005];
int v[2097160];

inline void Isprime()
{
    v[1] = 2;
    v[0] = 2;
    for (int i = 2; i <= 2097160; ++i)
    {
        if (v[i] == 0)
        {
            for (int j = i; j <= 2097160/i; ++j)
                v[i*j] = 2;
        }
    }
}
        
int main()
{
    freopen("Jelly.in", "r", stdin);
    freopen("Jelly.out", "w", stdout);
            
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    Isprime();    
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n; ++i)
        if(v[a[i]] == 0)
            f[i][i] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = i+1; j <= n; ++j)
        {
            f[i][j] = f[i][j-1]+f[j][j];
            int tmp = a[j];
            for(int k = j-1; k >= i; --k)
            {
                tmp |= a[k];   
                if(v[tmp] == 0)
                    f[i][j]++;
            }
        }
    
    for(int i = 1; i <= m; ++i)
    {
        int l, r;
        cin >> l >> r;
        cout << f[l][r] << '\n';
    }
        
   	return 0;
}