给你一个数组 $$$a_1, a_2, \ldots, a_n$$$。查找元组 ($$$x, y, z$$$) 的数量,使得:
- $$$1 \leq x \leq y \leq z \leq n$$$,以及
- $$$f(x, y) \oplus f(y, z) > f(x, z)$$$。
我们定义 $$$f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \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$$$。
输出
对于每个测试用例,在新行中输出一个整数 - 所描述元组的数量。
示例
输入 #1
3 3 6 2 4 1 3 5 7 3 7 2 1
输出 #1
4 0 16
注意
在第一种情况下,数组 $$$[6, 2, 4]$$$ 中有 4 个这样的元组:
- ($$$1$$$, $$$2$$$, $$$2$$$): $$$(a_1 \oplus a_2) \oplus (a_2) = 4 \oplus 2 > (a_1 \oplus a_2) = 4$$$
- ($$$1$$$, $$$1$$$, $$$3$$$): $$$(a_1) \oplus (a_1 \oplus a_2 \oplus a_3) = 6 \oplus 0 > (a_1 \oplus a_2 \oplus a_3) = 0$$$
- ($$$1$$$, $$$2$$$, $$$3$$$): $$$(a_1 \oplus a_2) \oplus (a_2 \oplus a_3) = 4 \oplus 6 > (a_1 \oplus a_2 \oplus a_3) = 0$$$
- ($$$1$$$, $$$3$$$, $$$3$$$): $$$(a_1 \oplus a_2 \oplus a_3) \oplus (a_3) = 0 \oplus 4 > (a_1 \oplus a_2 \oplus a_3) = 0$$$
在第二个测试用例中,没有这样的元组。