Du känner en kuf i Forgotten Hill. Idag vill denna kuf att du löser följande problem:

• Givet det $32$-dimensionella vektorrummet $\mathbb{F}_2^{32}$ över den ändliga kroppen $\mathbb{F}_2$ samt $n$ element $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ i det, beräkna $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Kufen berättade en gång för Lilla Cyanfisken (Little Cyan Fish) hur man löser hans problem. De relevanta minnena har dock suddats ut av kufen. Därför hoppas Lilla Cyanfisken att du kan lösa kufens problem. Om du inte är bekant med notationen ovan beskriver Lilla Cyanfisken problemet i naturligt språk enligt följande:

• Givet är en följd av icke-negativa heltal med längd $n$: $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Definiera värdet av $B(l, r)$ som mängden av alla möjliga XOR-värden som kan erhållas genom att välja ett godtyckligt antal tal (möjligen $0$) från $a_l, a_{l+1} \dots a_r$ och beräkna XOR av dem alla. Med andra ord: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Här betecknar $\oplus$ bitvis XOR. Till exempel är $4 \oplus 6 = 2$ och $1 \oplus 2 = 3$.
• Beräkna hur många olika mängder $B(l, r)$ det finns över alla $1 \le l \le r \le n$.

Indata

Detta problem innehåller flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden ett heltal $n$ ($1 \le n \le 10^5$).

Nästa rad innehåller $n$ heltal $a_i$ ($0 \le a_i < 2^{32}$).

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut en rad med ett heltal som anger antalet olika mängder $B(l, r)$, det vill säga $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Exempel

Indata 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

Utdata 1

4
10
12
36
46

Förklaring

För det första exempeltestfallet är de giltiga mängderna: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.