Du kjenner en raring i Forgotten Hill. I dag vil denne raringen at du skal løse følgende problem:

• Gitt det $32$-dimensjonale vektorrommet $\mathbb{F}_2^{32}$ over den endelige kroppen $\mathbb{F}_2$ samt $n$ elementer $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ i det, finn $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Raringen fortalte en gang Lille Cyanfisk (Little Cyan Fish) hvordan man løser problemet hans. De relevante minnene har imidlertid blitt visket ut av raringen. Derfor håper Lille Cyanfisk at du kan løse problemet til denne raringen. Hvis du ikke er kjent med notasjonen ovenfor, beskriver Lille Cyanfisk problemet i naturlig språk slik:

• Gitt en følge av ikke-negative heltall med lengde $n$: $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Definer verdien av $B(l, r)$ som mengden av alle mulige XOR-verdier som kan oppnås ved å velge et vilkårlig antall tall (muligens $0$) fra $a_l, a_{l+1} \dots a_r$ og ta XOR av dem alle sammen. Med andre ord: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Her betegner $\oplus$ bitvis XOR-operasjon. For eksempel er $4 \oplus 6 = 2$ og $1 \oplus 2 = 3$.
• Finn hvor mange forskjellige mengder $B(l, r)$ det finnes over alle $1 \le l \le r \le n$.

Inndata

Dette problemet inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($1 \le n \le 10^5$).

Den neste linjen inneholder $n$ heltall $a_i$ ($0 \le a_i < 2^{32}$).

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én linje med ett heltall som angir antall forskjellige mengder $B(l, r)$, det vil si $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Eksempel

Inndata 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

Forklaring

For det første eksempeltesttilfellet inkluderer de gyldige mengdene: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.