Conosci una persona eccentrica a Forgotten Hill. Oggi, questa persona eccentrica vuole che tu risolva il seguente problema:

• Dato lo spazio vettoriale di dimensione $32$ $\mathbb{F}_2^{32}$ sul campo finito $\mathbb{F}_2$ e $n$ suoi elementi $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$, trova $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

La persona eccentrica una volta aveva detto al Piccolo Pesce Ciano (Little Cyan Fish) come risolvere il suo problema. Tuttavia, i ricordi relativi sono stati offuscati dalla persona eccentrica. Pertanto, il Piccolo Pesce Ciano spera che tu possa risolvere il problema di questa persona eccentrica. Se non hai familiarità con la notazione sopra riportata, il Piccolo Pesce Ciano descrive il problema in linguaggio naturale come segue:

• Data una sequenza di interi non negativi di lunghezza $n$, $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Definisci il valore di $B(l, r)$ come l'insieme di tutti i possibili valori XOR ottenibili scegliendo un qualsiasi numero di elementi (anche $0$) da $a_l, a_{l+1} \dots a_r$ e calcolando lo XOR di tutti loro. In altre parole: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Dove $\oplus$ indica l'operazione di XOR bit a bit. Ad esempio, $4 \oplus 6 = 2$ e $1 \oplus 2 = 3$.
• Trova quanti insiemi distinti $B(l, r)$ esistono al variare di tutti gli $1 \le l \le r \le n$.

Input

Questo problema contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene un intero $n$ ($1 \le n \le 10^5$).

La riga successiva contiene $n$ interi $a_i$ ($0 \le a_i < 2^{32}$).

È garantito che la somma di $n$ su tutti i casi di test non superi $10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente un intero che indica il numero di insiemi distinti $B(l, r)$, ossia $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Esempio

Input 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

Output 1

4
10
12
36
46

Note

Per il primo caso di test di esempio, gli insiemi validi includono: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.