#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
struct BIT {
struct Foo {
long long s0 = 0;
int s1 = 0;
};
vector<Foo> dat;
BIT(int n) : dat(n + 1) {}
void update0(int k, long long v) {
for (int i = k + 1; i < dat.size(); i += i & -i) {
dat[i].s0 -= k * v;
dat[i].s1 += v;
}
}
long long query0(int k) {
long long res0 = 0;
long long res1 = 0;
for (int i = k; i > 0; i -= i & -i) {
res0 += dat[i].s0;
res1 += dat[i].s1;
}
return res0 + res1 * k;
}
void update(int l, int r, long long v) {
update0(l, v);
update0(r, -v);
}
long long query(int l, int r) {
return query0(r) - query0(l);
}
};
bool is_square(int n) {
int s = sqrt(n);
return s * s == n;
}
int main() {
int T;
cin >> T;
while (T--) {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
vector<int> ls(q), rs(q);
vector<vector<int>> es(n + 1);
for (int i = 0; i < q; i++) {
scanf("%d %d", &ls[i], &rs[i]);
ls[i]--;
es[rs[i]].push_back(i);
}
vector<long long> ans(q);
vector<pair<int, int>> vs;
vector<pair<int, int>> us;
BIT bit(n + 1);
for (int i = 0; i < n; i++) {
us.clear();
for (auto p : vs) {
int nv = p.first & a[i];
if (us.empty() || us.back().first != nv) {
us.emplace_back(nv, p.second);
}
}
if (us.empty() || us.back().first != a[i]) {
us.emplace_back(a[i], i);
}
swap(us, vs);
for (int j = 0; j < vs.size(); j++) {
if (is_square(vs[j].first)) {
if (j + 1 < vs.size()) {
bit.update(vs[j].second, vs[j + 1].second, 1);
} else {
bit.update(vs[j].second, i + 1, 1);
}
}
}
for (int j : es[i + 1]) {
ans[j] = bit.query(ls[j], i + 1);
}
}
for (int i = 0; i < q; i++) {
printf("%lld\n", ans[i]);
}
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxtYXA+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IEJJVCB7CiAgc3RydWN0IEZvbyB7CiAgICBsb25nIGxvbmcgczAgPSAwOwogICAgaW50IHMxID0gMDsKICB9OwogIHZlY3RvcjxGb28+IGRhdDsKCiAgQklUKGludCBuKSA6IGRhdChuICsgMSkge30KCiAgdm9pZCB1cGRhdGUwKGludCBrLCBsb25nIGxvbmcgdikgewogICAgZm9yIChpbnQgaSA9IGsgKyAxOyBpIDwgZGF0LnNpemUoKTsgaSArPSBpICYgLWkpIHsKICAgICAgZGF0W2ldLnMwIC09IGsgKiB2OwogICAgICBkYXRbaV0uczEgKz0gdjsKICAgIH0KICB9CgogIGxvbmcgbG9uZyBxdWVyeTAoaW50IGspIHsKICAgIGxvbmcgbG9uZyByZXMwID0gMDsKICAgIGxvbmcgbG9uZyByZXMxID0gMDsKICAgIGZvciAoaW50IGkgPSBrOyBpID4gMDsgaSAtPSBpICYgLWkpIHsKICAgICAgcmVzMCArPSBkYXRbaV0uczA7CiAgICAgIHJlczEgKz0gZGF0W2ldLnMxOwogICAgfQogICAgcmV0dXJuIHJlczAgKyByZXMxICogazsKICB9CgogIHZvaWQgdXBkYXRlKGludCBsLCBpbnQgciwgbG9uZyBsb25nIHYpIHsKICAgIHVwZGF0ZTAobCwgdik7CiAgICB1cGRhdGUwKHIsIC12KTsKICB9CgogIGxvbmcgbG9uZyBxdWVyeShpbnQgbCwgaW50IHIpIHsKICAgIHJldHVybiBxdWVyeTAocikgLSBxdWVyeTAobCk7CiAgfQp9OwoKYm9vbCBpc19zcXVhcmUoaW50IG4pIHsKICBpbnQgcyA9IHNxcnQobik7CiAgcmV0dXJuIHMgKiBzID09IG47Cn0KCmludCBtYWluKCkgewogIGludCBUOwogIGNpbiA+PiBUOwogIHdoaWxlIChULS0pIHsKICAgIGludCBuLCBxOwogICAgY2luID4+IG4gPj4gcTsKICAgIHZlY3RvcjxpbnQ+IGEobik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICBzY2FuZigiJWQiLCAmYVtpXSk7CiAgICB9CiAgICB2ZWN0b3I8aW50PiBscyhxKSwgcnMocSk7CiAgICB2ZWN0b3I8dmVjdG9yPGludD4+IGVzKG4gKyAxKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcTsgaSsrKSB7CiAgICAgIHNjYW5mKCIlZCAlZCIsICZsc1tpXSwgJnJzW2ldKTsKICAgICAgbHNbaV0tLTsKICAgICAgZXNbcnNbaV1dLnB1c2hfYmFjayhpKTsKICAgIH0KICAgIHZlY3Rvcjxsb25nIGxvbmc+IGFucyhxKTsKICAgIHZlY3RvcjxwYWlyPGludCwgaW50Pj4gdnM7CiAgICB2ZWN0b3I8cGFpcjxpbnQsIGludD4+IHVzOwogICAgQklUIGJpdChuICsgMSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICB1cy5jbGVhcigpOwogICAgICBmb3IgKGF1dG8gcCA6IHZzKSB7CiAgICAgICAgaW50IG52ID0gcC5maXJzdCAmIGFbaV07CiAgICAgICAgaWYgKHVzLmVtcHR5KCkgfHwgdXMuYmFjaygpLmZpcnN0ICE9IG52KSB7CiAgICAgICAgICB1cy5lbXBsYWNlX2JhY2sobnYsIHAuc2Vjb25kKTsKICAgICAgICB9CiAgICAgIH0KICAgICAgaWYgKHVzLmVtcHR5KCkgfHwgdXMuYmFjaygpLmZpcnN0ICE9IGFbaV0pIHsKICAgICAgICB1cy5lbXBsYWNlX2JhY2soYVtpXSwgaSk7CiAgICAgIH0KICAgICAgc3dhcCh1cywgdnMpOwogICAgICBmb3IgKGludCBqID0gMDsgaiA8IHZzLnNpemUoKTsgaisrKSB7CiAgICAgICAgaWYgKGlzX3NxdWFyZSh2c1tqXS5maXJzdCkpIHsKICAgICAgICAgIGlmIChqICsgMSA8IHZzLnNpemUoKSkgewogICAgICAgICAgICBiaXQudXBkYXRlKHZzW2pdLnNlY29uZCwgdnNbaiArIDFdLnNlY29uZCwgMSk7CiAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBiaXQudXBkYXRlKHZzW2pdLnNlY29uZCwgaSArIDEsIDEpOwogICAgICAgICAgfQogICAgICAgIH0KICAgICAgfQogICAgICBmb3IgKGludCBqIDogZXNbaSArIDFdKSB7CiAgICAgICAgYW5zW2pdID0gYml0LnF1ZXJ5KGxzW2pdLCBpICsgMSk7CiAgICAgIH0KICAgIH0KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcTsgaSsrKSB7CiAgICAgIHByaW50ZigiJWxsZFxuIiwgYW5zW2ldKTsKICAgIH0KICB9Cn0=