C. Четные подмассивы
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан целочисленный массив $$$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... Так, давайте закончим. Просто выведите сам ответ.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите количество подмассивов, $$$\operatorname{XOR}$$$ которых имеет четное количество делителей.

Пример
Входные данные
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
Примечание

В первом наборе входных данных есть $$$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}$$$ которых имеет четное количество делителей, так как $$$\operatorname{XOR}$$$ любого подмассива равен либо $$$4$$$, либо $$$0$$$.