Þú þekkir sérvitring í Forgotten Hill. Í dag vill þessi sérvitringur að þú leysir eftirfarandi verkefni:

• Gefum okkur $32$-víða vigurrúmið $\mathbb{F}_2^{32}$ yfir endanlega sviðið $\mathbb{F}_2$ og $n$ stök $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ í því. Finndu $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Sérvitringurinn sagði Litla Blágræna Fiskinum (Little Cyan Fish) eitt sinn hvernig ætti að leysa verkefnið hans. Hins vegar hefur sérvitringurinn gert viðeigandi minningar óskýrar. Því vonar Litli Blágræni Fiskurinn að þú getir leyst verkefni þessa sérvitrings. Ef þú þekkir ekki ritháttinn hér að ofan lýsir Litli Blágræni Fiskurinn verkefninu á náttúrulegu máli sem hér segir:

• Gefin er runa af ekki-neikvæðum heiltölum af lengd $n$: $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Skilgreinum gildi $B(l, r)$ sem mengi allra mögulegra XOR-gilda sem fást með því að velja hvaða fjölda talna sem er (mögulega $0$) úr $a_l, a_{l+1} \dots a_r$ og taka XOR af þeim öllum saman. Með öðrum orðum: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Hér táknar $\oplus$ bitbundna XOR-aðgerð. Til dæmis er $4 \oplus 6 = 2$ og $1 \oplus 2 = 3$.
• Finndu hversu mörg ólík mengi $B(l, r)$ eru til fyrir öll $1 \le l \le r \le n$.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan heiltölu $n$ ($1 \le n \le 10^5$).

Næsta lína inniheldur $n$ heiltölur $a_i$ ($0 \le a_i < 2^{32}$).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta út eina línu sem inniheldur heiltölu sem táknar fjölda ólíkra mengja $B(l, r)$, þ.e. $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Dæmi

Inntak 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

Úttak 1

4
10
12
36
46

Skýring

Fyrir fyrsta prófunartilvikið í dæminu eru gildu mengin: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.