问题描述

在数据王国的边境线上，有一排由神秘数字构成的魔法城墙。这些数字蕴含着强大的能量，王国的大法师们发现，只有当特定的三元组满足某种位运算不等式时，才能激活城墙的防御魔法。

作为王国的首席算法工程师，你需要编写一个高效的程序，计算出所有符合条件的魔法三元组数量，帮助王国加强边境防御。

给定一个正整数数组 $a_1, a_2, \ldots, a_n$，统计满足以下条件的三元组 $(x, y, z)$ 的个数：

1. $1 \leq x \leq y \leq z \leq n$，且
2. $f(x, y) \oplus f(y, z) > f(x, z)$

其中，$f(l, r) = a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$，$\oplus$ 表示按位异或运算。

输入格式

• 第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。
• 每个测试用例包含两行：
  • 第一行：一个整数 $n$（$1 \leq n \leq 10^5$），表示数组的长度。
  • 第二行：$n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组元素，数字间用空格分隔。
• 保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的三元组数量。

样例输入

3
3
6 2 4
1
3
5
7 3 7 2 1

样例输出

4
0
16

说明

对于数组 $[6, 2, 4]$，满足条件的三元组有：

1. $(1,2,2)$: $(6\oplus2)\oplus2 = 4\oplus2=6 > 4$
2. $(1,1,3)$: $6\oplus(6\oplus2\oplus4) = 6\oplus0=6 > 0$
3. $(1,2,3)$: $(6\oplus2)\oplus(2\oplus4) = 4\oplus6=2 > 0$
4. $(1,3,3)$: $(6\oplus2\oplus4)\oplus4 = 0\oplus4=4 > 0$

第二个测试用例没有满足条件的三元组。