Вам дан массив \(a_1, a_2, \ldots, a_n\). Найдите количество троек чисел (\(x, y, 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\).
Для каждого набора входных данных выведите в отдельной строке одно целое число — количество подходящих троек.
В первом наборе входных данных для массива \([6, 2, 4]\) есть 4 подходящие тройки чисел:
Во втором наборе входных данных подходящих троек нет.
3 3 6 2 4 1 3 5 7 3 7 2 1
4 0 16
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач