Vous connaissez une personne excentrique à Forgotten Hill. Aujourd'hui, cette personne excentrique souhaite que vous résolviez le problème suivant :

• Étant donné l'espace vectoriel de dimension $32$ $\mathbb{F}_2^{32}$ sur le corps fini $\mathbb{F}_2$ ainsi que $n$ éléments $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ de cet espace, trouvez $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

La personne excentrique avait autrefois expliqué à Petit Poisson Cyan (Little Cyan Fish) comment résoudre son problème. Cependant, les souvenirs correspondants ont été brouillés par la personne excentrique. C'est pourquoi Petit Poisson Cyan espère que vous pourrez résoudre le problème de cette personne excentrique. Si vous n'êtes pas familier avec les notations ci-dessus, Petit Poisson Cyan décrit le problème en langage naturel comme suit :

• On vous donne une suite d'entiers naturels de longueur $n$ : $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• On définit la valeur de $B(l, r)$ comme l'ensemble de toutes les valeurs de OU exclusif (XOR) possibles obtenues en choisissant un nombre quelconque d'éléments (éventuellement $0$) parmi $a_l, a_{l+1} \dots a_r$ et en effectuant leur XOR à tous. Autrement dit : $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Où $\oplus$ désigne l'opération XOR bit à bit. Par exemple, $4 \oplus 6 = 2$ et $1 \oplus 2 = 3$.
• Déterminez combien il existe d'ensembles distincts $B(l, r)$ sur tous les couples $1 \le l \le r \le n$.

Entrée

Ce problème comporte plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 10^5$).

La ligne suivante contient $n$ entiers $a_i$ ($0 \le a_i < 2^{32}$).

Il est garanti que la somme des $n$ sur tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier représentant le nombre d'ensembles distincts $B(l, r)$, c'est-à-dire $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Exemple

Entrée 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

Sortie 1

4
10
12
36
46

Note

Pour le premier cas de test de l'exemple, les ensembles valides sont : $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.