#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll bitvalue(ll x, ll y){
    x=x/pow(2,y);
    return x%2;
}
int main() {
    // your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        ll n,q;
        cin>>n>>q;
        ll a[65][n], countzero[64][n]={0}, countone[64][n]={0};
        for (ll i=0; i<n; i++) cin>>a[64][i];
        for (ll j=0; j<64; j++){
            for (ll i=0; i<n; i++){
                a[j][i]=bitvalue(a[64][i],j);
                if (a[j][i]==0){
                    countzero[j][i]=countzero[j][i-1]+1;
                    countone[j][i]=countone[j][i-1];
                }
                if (a[j][i]==1){
                    countone[j][i]=countone[j][i-1]+1;
                    countzero[j][i]=countzero[j][i-1];
                }
            }
        }
        while(q--){
            ll k,l1,r1,l2,r2;
            cin>>k>>l1>>r1>>l2>>r2;
            if (l1>1 && l2>1){
                ll e=(countzero[k][r1-1]-countzero[k][l1-2])*(countone[k][r2-1]-countone[k][l2-2])+(countone[k][r1-1]-countone[k][l1-2])*(countzero[k][r2-1]-countzero[k][l2-2]);
                cout<<e<<"\n";
            }
            else {
                if (l1==1){
                    ll e=(countzero[k][r1-1])*(countone[k][r2-1]-countone[k][l2-2])+(countone[k][r1-1])*(countzero[k][r2-1]-countzero[k][l2-2]);
                    cout<<e<<"\n";
                }
            }
        }
    }
    return 0;
}