Conoces a una persona excéntrica en Forgotten Hill. Hoy, esta persona excéntrica quiere que resuelvas el siguiente problema:

• Dado el espacio vectorial de dimensión $32$ $\mathbb{F}_2^{32}$ sobre el cuerpo finito $\mathbb{F}_2$ y $n$ elementos $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ en él, halla $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

La persona excéntrica le contó una vez al Pequeño Pez Cian (Little Cyan Fish) cómo resolver su problema. Sin embargo, los recuerdos correspondientes han sido difuminados por la persona excéntrica. Por lo tanto, el Pequeño Pez Cian espera que puedas resolver el problema de esta persona excéntrica. Si no estás familiarizado con la notación anterior, el Pequeño Pez Cian describe el problema en lenguaje natural de la siguiente manera:

• Dada una secuencia de enteros no negativos de longitud $n$, $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Se define el valor de $B(l, r)$ como el conjunto de todos los posibles valores XOR obtenidos al elegir cualquier cantidad de números (posiblemente $0$) entre $a_l, a_{l+1} \dots a_r$ y aplicarles la operación XOR a todos ellos. En otras palabras: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Donde $\oplus$ denota la operación XOR bit a bit. Por ejemplo, $4 \oplus 6 = 2$ y $1 \oplus 2 = 3$.
• Halla cuántos conjuntos distintos $B(l, r)$ existen para todos los $1 \le l \le r \le n$.

Entrada

Este problema contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($1 \le n \le 10^5$).

La siguiente línea contiene $n$ enteros $a_i$ ($0 \le a_i < 2^{32}$).

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con un entero que represente la cantidad de conjuntos distintos $B(l, r)$, es decir, $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Ejemplo

Entrada 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

Salida 1

4
10
12
36
46

Nota

Para el primer caso de prueba de ejemplo, los conjuntos válidos incluyen: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.