#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
ifstream fin("Jelly.in");
ofstream fout("Jelly.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 1e5 + 5, M = 1048580;
int n = mread(), m = mread(), a[N], ans[M], f[25][N], s[N * 5], lzk[N * 5], lzc[N * 5];
vector<pair<int, int> > v[N];
bool e[M];
vector<int> p;
void add2(int x, int nl, int nr, int l, int r, int k, int c){
    int fi = k + (nl - l) * c, la = k + (nr - l) * c;
    s[x] += (fi + la) * (nr - nl + 1) / 2;
    lzk[x] += fi, lzc[x] += c;
    return;
}
void pushdown(int x, int nl, int nr){
    if(lzk[x] == 0 && lzc[x] == 0)
    return;
    int mid = nl + nr >> 1;
    add2(x << 1, nl, mid, nl, nr, lzk[x], lzc[x]);
    add2(x << 1 | 1, mid + 1, nr, nl, nr, lzk[x], lzc[x]);
    lzk[x] = lzc[x] = 0;
    return;
}
void pushup(int x){
    s[x] = s[x << 1] + s[x << 1 | 1];
}
void add(int x, int nl, int nr, int l, int r, int k, int c){
//    printf("--- %lld %lld %lld %lld %lld %lld %lld\n", x, nl, nr, l, r, k, c);
    if(nl >= l && nr <= r){
        add2(x, nl, nr, l, r, k, c);
        return;
    }
    pushdown(x, nl, nr);
    int mid = nl + nr >> 1;
    if(mid >= l)
    add(x << 1, nl, mid, l, r, k, c);
    if(mid + 1 <= r)
    add(x << 1 | 1, mid + 1, nr, l, r, k, c);
    pushup(x);
    return;
}
int query(int x, int nl, int nr, int p){
    if(nl == nr)
    return s[x];
    pushdown(x, nl, nr);
    int mid = nl + nr >> 1;
    int ans;
    if(p <= mid)
    ans = query(x << 1, nl, mid, p);
    else
    ans = query(x << 1 | 1, mid + 1, nr, p);
    pushup(x);
    return ans;
}
int makeOr(int l, int r){
    int lg = __lg(r - l + 1);
    return f[lg][l] | f[lg][r - (1 << lg) + 1];
}
void cg(int now, int x){
    int l = 1, r = now;
    while(l < r){
        int mid = l + r >> 1;
        if((makeOr(mid, now) | x) == x)
        r = mid;
        else
        l = mid + 1;
    }
//    if(now > 95000)
//    printf("*** %lld %lld %lld %lld\n", l, now, x, makeOr(l, now));
    if(e[x] == 0){
        add(1, 1, n, l, now, now - l + 1, -1);
//        printf("*** %lld %lld %lld %lld\n", l, now, now - l + 1, -1ll);
        if(l > 1){
            add(1, 1, n, 1, l - 1, now - l + 1, 0);
//            printf("*** %lld %lld %lld %lld\n", 1ll, l - 1, now - l + 1, 0ll);
        }
//        for(int j = 1; j <= n; j ++)
//        printf("%lld ", query(1, 1, m, j));
//        printf("\n");
    }
    if(l > 1)
    cg(l - 1, x | a[l - 1]);
    return;
}
signed main(){
    e[0] = e[1] = 1;
    for(int i = 2; i < M; i ++){
        if(e[i] == 0){
            p.push_back(i);
        }
        for(int j = 0; j < p.size(); j ++){
            if(p[j] * i >= M)
            break;
            e[p[j] * i] = 1;
            if(i % p[j] == 0)
            break;
        }
    }
    for(int i = 1; i <= n; i ++)
    f[0][i] = a[i] = mread();
    for(int j = 1; j <= 20; j ++){
        for(int i = 1; i <= n - (1 << j) + 1; i ++)
        f[j][i] = f[j - 1][i] | f[j - 1][i + (1 << j - 1)];
    }
    for(int i = 1; i <= m; i ++){
        int l = mread(), r = mread();
        v[r].push_back(mp(l, i));
    }
    for(int i = 1; i <= n; i ++){
//        if(i > 95000)
//        printf("*** %lld\n", i);
        cg(i, a[i]);
//        for(int j = 1; j <= n; j ++)
//        printf("%lld ", query(1, 1, m, j));
//        printf("\n");
        for(auto t : v[i]){
            ans[t.se] = query(1, 1, n, t.fi);
//            printf("*** %lld %lld %lld\n", t.fi, i, query(1, 1, n, t.fi));
        }
    }
    for(int i = 1; i <= m; i ++)
    fout << ans[i] << "\n";
//    printf("%lld\n", ans[i]);
    return 0;
}