Du kennst einen Sonderling in Forgotten Hill. Heute möchte dieser Sonderling, dass du das folgende Problem löst:

• Gegeben seien der $32$-dimensionale Vektorraum $\mathbb{F}_2^{32}$ über dem endlichen Körper $\mathbb{F}_2$ sowie $n$ Elemente $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ darin. Bestimme $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Der Sonderling hat dem Kleinen Cyanfisch (Little Cyan Fish) einst verraten, wie man sein Problem löst. Allerdings wurden die entsprechenden Erinnerungen vom Sonderling verwischt. Daher hofft der Kleine Cyanfisch, dass du das Problem dieses Sonderlings lösen kannst. Falls du mit der obigen Notation nicht vertraut bist, beschreibt der Kleine Cyanfisch das Problem in natürlicher Sprache wie folgt:

• Gegeben sei eine Folge nichtnegativer ganzer Zahlen der Länge $n$: $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Definiere den Wert von $B(l, r)$ als die Menge aller möglichen XOR-Werte, die man erhält, indem man beliebig viele Zahlen (möglicherweise $0$) aus $a_l, a_{l+1} \dots a_r$ auswählt und sie alle miteinander XOR-verknüpft. Mit anderen Worten: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Dabei bezeichnet $\oplus$ die bitweise XOR-Verknüpfung. Beispielsweise gilt $4 \oplus 6 = 2$ und $1 \oplus 2 = 3$.
• Bestimme, wie viele paarweise verschiedene Mengen $B(l, r)$ es über alle $1 \le l \le r \le n$ gibt.

Eingabe

Dieses Problem enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($1 \le n \le 10^5$).

Die nächste Zeile enthält $n$ ganze Zahlen $a_i$ ($0 \le a_i < 2^{32}$).

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die die Anzahl der verschiedenen Mengen $B(l, r)$ angibt, d. h. $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Beispiel

Eingabe 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

Ausgabe 1

4
10
12
36
46

Hinweis

Für den ersten Beispieltestfall umfassen die gültigen Mengen: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.