Untitled

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void init()
{
	cin.tie(0);
	cin.sync_with_stdio(0);
}

const int MAX_CHAR = 2, max_bits = 21;

struct Trie
{
	Trie *child[MAX_CHAR];
	int fre[2];

	Trie()
	{
		memset(child, 0, sizeof(child));
		memset(fre, 0, sizeof(fre));
	}

	void insert(int i, int &x)
	{
		if (i < 0)
			return;

		bool cur = (x & (1 << i));
		fre[cur]++;

		if (child[cur] == 0)
			child[cur] = new Trie();
		child[cur]->insert(i - 1, x);
	}

	void query(int i, int &x, int &max_, long long &ans)
	{
		if (i < 0)
			return;

		bool cur = (x & (1 << i));
		bool cur_max = (max_ & (1 << i));

		if (cur_max == 0)
			ans += fre[!cur];

		cur = cur ^ cur_max;
		if (child[cur] == 0)
			return;

		child[cur]->query(i - 1, x, max_, ans);
	}

	void dele(int i)
	{
		if (i < 0)
			return;

		if (child[0] != 0)
		{
			child[0]->dele(i - 1);
			delete child[0];
		}

		if (child[1] != 0)
		{
			child[1]->dele(i - 1);
			delete child[1];
		}
	}
};

long long ans = 0;
void solve(int l, int r, vector<int> &v)
{
	if (l >= r)
		return;

	int mid = (l + r) >> 1;

	solve(l, mid, v);
	solve(mid + 1, r, v);

	int max_r = 0, max_l = 0;
	long long fre = 0;

	Trie left, right;

	int j = mid;
	for (int i = mid; i >= l; i--)
	{
		max_r = max(max_r, v[i]);

		while (j + 1 <= r && max(max_l, v[j + 1]) <= max_r)
		{
			j++;
			max_l = max(max_l, v[j]);

			fre = 0;
			right.query(max_bits, v[j], max_l, fre);
			ans += fre * max_l;

			left.insert(max_bits, v[j]);
		}

		fre = 0;
		left.query(max_bits, v[i], max_r, fre);
		ans += fre * max_r;

		right.insert(max_bits, v[i]);
	}

	while (j + 1 <= r)
	{
		j++;
		max_l = max(max_l, v[j]);

		fre = 0;
		right.query(max_bits, v[j], max_l, fre);
		ans += fre * max_l;
	}

	left.dele(max_bits);
	right.dele(max_bits);
}

int main()
{
	init();
	// freopen("mootube.in", "r", stdin);
	// freopen("mootube.out", "w", stdout);
	int t;
	cin >> t;

	while (t--)
	{
		int n;
		cin >> n;

		vector<int> v(n);
		for (int i = 0; i < n; i++)
			cin >> v[i];

		ans = 0;
		solve(0, n - 1, v);
		cout << ans << "\n";
	}

	return 0;
}