CF1731C.Even Subarrays

You are given an integer array $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Find the number of subarrays of $a$ whose $\operatorname{XOR}$ has an even number of divisors. In other words, find all pairs of indices $(i, j)$ ($i \le j$) such that $a_i \oplus a_{i + 1} \oplus \dots \oplus a_j$ has an even number of divisors.

For example, numbers $2$, $3$, $5$ or $6$ have an even number of divisors, while $1$ and $4$ — odd. Consider that $0$ has an odd number of divisors in this task.

Here $\operatorname{XOR}$ (or $\oplus$) denotes the bitwise XOR operation.

Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer.

给你一个整数数组 $a_1, a_2, \dots, a_n$（其中 $1 \le a_i \le n$）。

请你找出数组 $a$ 中有多少个子数组，其异或值（$\operatorname{XOR}$）具有偶数个正因数。换句话说，求满足条件的下标对 $(i, j)$（其中 $i \le j$）的个数，使得 $a_i \oplus a_{i + 1} \oplus \dots \oplus a_j$ 具有偶数个正因数。

例如，数字 $2$、$3$、$5$ 和 $6$ 均有偶数个正因数，而 $1$ 和 $4$ 则有奇数个正因数。本题中规定：$0$ 被视为具有奇数个正因数。

此处 $\operatorname{XOR}$（或记作 $\oplus$）表示按位异或运算。

请输出满足条件的子数组个数（注意：不要乘以 2022……好了，我们停一下。只需输出真实的答案即可）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）—— 表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print the number of subarrays, whose $\operatorname{XOR}$ has an even number of divisors.

对于每个测试用例，输出满足其异或（$\operatorname{XOR}$）值具有偶数个约数的子数组个数。

In the first test case, there are $4$ subarrays whose $\operatorname{XOR}$ has an even number of divisors: $[3]$, $[3,1]$, $[1,2]$, $[2]$.

In the second test case, there are $11$ subarrays whose $\operatorname{XOR}$ has an even number of divisors: $[4,2]$, $[4,2,1]$, $[4,2,1,5]$, $[2]$, $[2,1]$, $[2,1,5]$, $[2,1,5,3]$, $[1,5,3]$, $[5]$, $[5,3]$, $[3]$.

In the third test case, there is no subarray whose $\operatorname{XOR}$ has an even number of divisors since $\operatorname{XOR}$ of any subarray is either $4$ or $0$.

在第一个测试用例中，有 $4$ 个子数组的异或值（$\operatorname{XOR}$）具有偶数个约数：$[3]$、$[3,1]$、$[1,2]$、$[2]$。

在第二个测试用例中，有 $11$ 个子数组的异或值（$\operatorname{XOR}$）具有偶数个约数：$[4,2]$、$[4,2,1]$、$[4,2,1,5]$、$[2]$、$[2,1]$、$[2,1,5]$、$[2,1,5,3]$、$[1,5,3]$、$[5]$、$[5,3]$、$[3]$。

在第三个测试用例中，不存在异或值（$\operatorname{XOR}$）具有偶数个约数的子数组，因为任意子数组的异或值要么是 $4$，要么是 $0$。