Дана последовательность $$$a$$$, состоящая из $$$n$$$ целых неотрицательных чисел.
Для последовательности $$$b$$$, состоящей из $$$k$$$ целых неотрицательных чисел, определим точечное увеличение последовательности $$$b$$$ как следующую операцию:
Пусть $$$f(b)$$$ — минимальное значение $$$b_1 \oplus b_2 \oplus \ldots \oplus b_k$$$ после выполнения точечного увеличения последовательности $$$b$$$ ровно один раз.$$$^{\text{∗}}$$$
Найдите значение следующей суммы.
$$$$$$\sum_{1 \le l \le r \le n}f([a_l,a_{l+1},\ldots,a_r])$$$$$$
$$$^{\text{∗}}$$$Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$).
Вторая строка каждого набора входных данных содержит целые числа $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt 2^{25}$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$4\cdot 10^5$$$.
Для каждого набора входных данных выведите ответ на задачу в отдельной строке.
455 4 6 7 553 3 2 2 3167101827481 5921082 14619611 643973 6718274 2948 244716 29 0 6717827
43216736695941
В первом наборе входных данных в качестве примера рассмотрим $$$f([5,4,6,7,5])$$$.
Если увеличить $$$b_2=4$$$ на $$$1$$$, то $$$b$$$ станет равна $$$[5,5,6,7,5]$$$, а $$$5 \oplus 5 \oplus 6 \oplus 7 \oplus 5 = 4$$$.
Можно доказать, что после одного точечного увеличения значение $$$b_1 \oplus b_2 \oplus b_3 \oplus b_4 \oplus b_5$$$ не может быть меньше $$$4$$$.
Можно доказать, что сумма минимальных значений по всем подмассивам равна $$$43$$$.
