#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, t, l, r, a[100005];
ll d[2][100005], ans[500005];
vector< pair<int, int> > rs[100005];
//vector for groups with equal AND
vector< pair<int, int> > groups;
//fenwick tree
ll sum(ll num, ll pos)
{
    ll sm = 0;
    while(pos >= 0)
    {
        sm += d[num][pos];
        pos = (pos & (pos + 1)) - 1;
    }
    return sm;
}
void update(ll num, ll pos, ll x)
{
    while(pos < n)
    {
        d[num][pos] += x;
        pos = (pos | (pos + 1));
    }
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        scanf("%d", &m);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            d[0][i] = d[1][i] = 0;
            rs[i].clear();
        }
        d[0][n] = d[1][n] = 0;
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &l, &r);
            l--;
            r--;
            rs[r].push_back({l, i});
        }
        groups.clear();
        for(int i = 0; i < n; i++)
        {
            //new vector for groups
            vector< pair<int, int> > newgroups;
            for(int j = 0; j < groups.size(); j++)
            {
                int cur = groups[j].first & a[i];
                if(!j || cur != newgroups[newgroups.size() - 1].first)
                {
                    newgroups.push_back({cur, groups[j].second});
                }
            }
            if(newgroups.size() == 0 || newgroups[newgroups.size() - 1].first != a[i])
                newgroups.push_back({a[i], i});
            //making new vector current
            groups = newgroups;
            for(int j = 0; j < groups.size(); j++)
            {
                //checking for a perfect square
                int sq = floor(sqrt(groups[j].first));
                if((sq - 1) * (sq - 1) == groups[j].first || sq * sq == groups[j].first || (sq + 1) * (sq + 1) == groups[j].first)
                {
                    //getting a borders
                    l = groups[j].second;
                    if(j != groups.size() - 1)
                        r = groups[j + 1].second - 1;
                    else
                        r = i;
                    //adding an arithmetic progression
                    update(0, l, (r + 1));
                    update(0, r + 1, -(r + 1));
                    update(1, l, 1);
                    update(1, r + 1, -1);
                    //adding on a prefix
                    update(0, 0, r - l + 1);
                    update(0, l, -(r - l + 1));
                }
            }
            for(int j = 0; j < rs[i].size(); j++)
            {
                //getting an answer for a query
                ans[rs[i][j].second] = sum(0, rs[i][j].first);
                ans[rs[i][j].second] -= sum(1, rs[i][j].first) * rs[i][j].first;
            }
        }
        for(int i = 0; i < m; i++)
        {
            printf("%lld\n", ans[i]);
        }
    }
    return 0;
}