该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

33DAI 面前有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 颗。

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$。称 $[l, r]$（$1 \le l \le r \le n$）是一个 连续子段，它的异或和为 $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$， 其中 $\oplus$ 表示按位异或：把两个整数写成二进制后逐位比较，该位相同则结果的这一位是 $0$，不同则是 $1$。在 C++ 中，按位异或写成 ^（例如 a ^ b）。

记正整数 $x$ 的正因子个数为 $d(x)$。特别地，本题规定 $0$ 的正因子个数是奇数 （可以理解为 $0$ 的因子个数“不是偶数”）。

33DAI 想知道：有多少个连续子段，满足其异或和 $x$ 的 $d(x)$ 是偶数？

本题有多组测试数据。

输入格式

从文件 xor.in 读入数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

接下来依次给出 $T$ 组数据，每组数据的格式为：

第一行包含一个整数 $n$，表示序列长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻两个整数之间用一个空格分隔。

输出格式

输出到文件 xor.out。

对于每组数据，输出一行一个整数，表示异或和的正因子个数为偶数的连续子段数量。

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

4
11
0
20

样例 1 解释

第一组数据：全部 $6$ 个连续子段中，$[3]$、$[3,1]$、$[1,2]$、$[2]$ 这 $4$ 个的异或和分别是 $3, 2, 3, 2$，正因子个数都是偶数；而 $[3,1,2]$ 的异或和是 $0$，$[1]$ 的异或和是 $1$， 按本题规定它们的正因子个数都是奇数，不计入答案。

第三组数据：没有连续子段满足条件，答案为 $0$。

样例 2

见 xor2.in 与 xor2.ans。

样例 3

见 xor3.in 与 xor3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le T \le 10^4$；
• $2 \le n \le 2 \times 10^5$；
• $1 \le a_i \le n$；
• 单个测试文件中所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。