Even Subarrays
Contest: Codeforces Round 841 (Div. 2) and Divide by Zero 2022
Difficulty rating: 1700
Tags: bitmasks, brute force, hashing, math, number theory

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3

Example output:
4
11
0
20

Editorial:
Let's calculate the number of subarrays whose $$$\operatorname{XOR}$$$ sum has an odd number of divisors and subtract them from total no of subarrays.
Note: A number has an odd number of divisors only if it is a perfect square. So we have to calculate number of subarray having $$$\operatorname{XOR}$$$ sum a perfect square.
For the given constraints for elements in the array, the maximum possible $$$\operatorname{XOR}$$$ sum of any subarray will be less than $$$2n$$$, so the number of possible elements with odd divisors $$$\leq \sqrt{2n}$$$. Number of subarrays with a given $$$\operatorname{XOR}$$$ sum can be calculated in $$$O(n)$$$.
Therefore, calculate the same for each perfect square less than $$$2n$$$ and add all these to get the number of subarrays whose $$$\operatorname{XOR}$$$ sum has an odd number of divisors. Subtract from total number of subarrays to get the required answer.
Time complexity : $$$O(n \cdot \sqrt{n})$$$.