D. Битовое неравенство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$. Найдите количество троек чисел ($$$x, y, z$$$) таких, что:

  • $$$1 \leq x \leq y \leq z \leq n$$$, и
  • $$$f(x, y) \oplus f(y, z) > f(x, 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$$$.

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

Для каждого набора входных данных выведите в отдельной строке одно целое число — количество подходящих троек.

Пример
Входные данные
3
3
6 2 4
1
3
5
7 3 7 2 1
Выходные данные
4
0
16
Примечание

В первом наборе входных данных для массива $$$[6, 2, 4]$$$ есть 4 подходящие тройки чисел:

  • ($$$1$$$, $$$2$$$, $$$2$$$): $$$(a_1 \oplus a_2) \oplus (a_2) = 4 \oplus 2 > (a_1 \oplus a_2) = 4$$$
  • ($$$1$$$, $$$1$$$, $$$3$$$): $$$(a_1) \oplus (a_1 \oplus a_2 \oplus a_3) = 6 \oplus 0 > (a_1 \oplus a_2 \oplus a_3) = 0$$$
  • ($$$1$$$, $$$2$$$, $$$3$$$): $$$(a_1 \oplus a_2) \oplus (a_2 \oplus a_3) = 4 \oplus 6 > (a_1 \oplus a_2 \oplus a_3) = 0$$$
  • ($$$1$$$, $$$3$$$, $$$3$$$): $$$(a_1 \oplus a_2 \oplus a_3) \oplus (a_3) = 0 \oplus 4 > (a_1 \oplus a_2 \oplus a_3) = 0$$$

Во втором наборе входных данных подходящих троек нет.