Вы знакомы с одним чудаком на Забытом Холме (Forgotten Hill). Сегодня этот чудак хочет, чтобы вы решили следующую задачу:

• Дано $32$-мерное векторное пространство $\mathbb{F}_2^{32}$ над конечным полем $\mathbb{F}_2$ и $n$ его элементов $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$. Найдите $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Когда-то чудак рассказал Маленькой Голубой Рыбке (Little Cyan Fish), как решить его задачу. Однако соответствующие воспоминания были размыты чудаком. Поэтому Маленькая Голубая Рыбка надеется, что вы сможете решить задачу этого чудака. Если вам незнакомы приведённые выше обозначения, Маленькая Голубая Рыбка описывает эту задачу на естественном языке следующим образом:

• Дана последовательность неотрицательных целых чисел длины $n$: $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Определим значение $B(l, r)$ как множество всех возможных значений исключающего ИЛИ (XOR), которые можно получить, выбрав произвольное количество чисел (возможно, $0$) из $a_l, a_{l+1} \dots a_r$ и применив ко всем ним операцию XOR. Иными словами: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Здесь $\oplus$ обозначает побитовую операцию исключающего ИЛИ. Например, $4 \oplus 6 = 2$, $1 \oplus 2 = 3$.
• Найдите, сколько существует различных множеств $B(l, r)$ по всем $1 \le l \le r \le n$.

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

В этой задаче несколько наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит одно целое число $n$ ($1 \le n \le 10^5$).

Следующая строка содержит $n$ целых чисел $a_i$ ($0 \le a_i < 2^{32}$).

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $10^5$.

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

Для каждого набора входных данных выведите одну строку, содержащую одно целое число — количество различных множеств $B(l, r)$, то есть $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Пример

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

5
3
1 2 3
4
10 12 17 33
6
1 0 9 8 7 3
8
9012 91829 9819 78 237 862 7672 2
10
0 1 2 4 8 16 32 64 128 256

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

4
10
12
36
46

Примечание

В первом тестовом примере подходящими множествами являются: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.