#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int kMaxN = 1e5, kMaxLog = 17, kMaxLogVal = 30, kMaxQ = 5e5;

int range_and[kMaxLog][kMaxN];
int logarithm[kMaxN + 1];
tuple<int, int, int> square_and_intervals[kMaxLogVal * kMaxN];
pair<int, int> queries[kMaxQ];
int query_idx[kMaxQ];
int64 result[kMaxQ];
int64 fen1[kMaxN], fen2[kMaxN];
int n;

unordered_set<int> squares;

void Init() {
    logarithm[2] = 1;
    for (int i = 3; i <= kMaxN; ++i) {
        logarithm[i] = logarithm[i / 2] + 1;
    }
    
    squares.reserve(1 << 15);
    for (int i = 0; i < (1 << 15); ++i) {
        squares.insert(i * i);
    }
}

int RangeAnd(const int l, const int r) {
    const int log_length = logarithm[r - l + 1];
    return range_and[log_length][l] & range_and[log_length][r - (1 << log_length) + 1];
}

bool IsSquare(const int x) {
    return squares.find(x) != squares.end();
}

void Update(int64 fenwick[], int pos, const int value) {
    for (; pos < n; pos |= pos + 1) {
        fenwick[pos] += value;
    }
}

int64 Query(int64 fenwick[], int pos) {
    int64 res = 0;
    while (pos >= 0) {
        res += fenwick[pos];
        pos = (pos & (pos + 1)) - 1;
    }
    return res;
}

int64 SumPrefix(const int l) {
    return Query(fen1, l) * l + Query(fen2, l);
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    
    Init();
    
    int num_tests; cin >> num_tests;
    while (num_tests--> 0) {
        int q; cin >> n >> q;
        for (int i = 0; i < n; ++i) {
            cin >> range_and[0][i];
        }        
        
        for (int l = 0; (1 << l + 1) <= n; ++l) {
            for (int i = 0; i + (1 << l + 1) - 1 < n; ++i) {
                range_and[l + 1][i] = range_and[l][i] & range_and[l][i + (1 << l)];
            }
        }
        
        int num_square_and_intervals = 0;
        for (int i = 0; i < n; ++i) {
            int pos = i;
            while (pos != n) {
                int value = RangeAnd(i, pos);
                int lo = pos - 1, hi = n;
                while (hi - lo > 1) {
                    int mid = (lo + hi) / 2;
                    if (value != RangeAnd(i, mid)) {
                        hi = mid;
                    } else {
                        lo = mid;
                    }
                }
                
                if (IsSquare(value)) {  // [i, pos..lo]
                    square_and_intervals[num_square_and_intervals++] = make_tuple(i, pos, lo);
                }
                
                pos = hi;
            }
        }
        
        sort(square_and_intervals, square_and_intervals + num_square_and_intervals);
        
        for (int i = 0; i < q; ++i) {
            cin >> queries[i].first >> queries[i].second;
            --queries[i].first; --queries[i].second;
            query_idx[i] = i;
        }
        
        sort(query_idx, query_idx + q, [](const int a, const int b) {
           return queries[a].first > queries[b].first; 
        });
        
        for (int i = 0; i < n; ++i) {
            fen1[i] = fen2[i] = 0;
        }
        for (int i = 0, j = num_square_and_intervals - 1; i < q; ++i) {
            while (j >= 0 and get<0>(square_and_intervals[j]) >= queries[query_idx[i]].first) {
                int lo, hi; tie(ignore, lo, hi) = square_and_intervals[j];
                Update(fen1, lo, +1);
                Update(fen1, hi, -1);
                Update(fen2, lo, -lo + 1);
                Update(fen2, hi, hi);
                --j;
            }
            
            result[query_idx[i]] = SumPrefix(queries[query_idx[i]].second);
        }
        
        for (int i = 0; i < q; ++i) {
            cout << result[i] << '\n';
        }
    }
}