Tunnet erään kummajaisen Forgotten Hillissä. Tänään tämä kummajainen haluaa sinun ratkaisevan seuraavan tehtävän:

• Annetaan äärellisen kunnan $\mathbb{F}_2$ päällä oleva $32$-ulotteinen vektoriavaruus $\mathbb{F}_2^{32}$ sekä sen $n$ alkiota $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$. Etsi $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Kummajainen kertoi kerran Pienelle Syaanikalalle (Little Cyan Fish), kuinka hänen tehtävänsä ratkaistaan. Kummajainen on kuitenkin hämärtänyt asiaan liittyvät muistot. Siksi Pieni Syaanikala toivoo, että pystyt ratkaisemaan tämän kummajaisen tehtävän. Jos yllä oleva merkintätapa ei ole sinulle tuttu, Pieni Syaanikala kuvailee tehtävän luonnollisella kielellä seuraavasti:

• Annetaan pituutta $n$ oleva ei-negatiivisten kokonaislukujen jono $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Määritellään joukon $B(l, r)$ arvoksi kaikkien niiden mahdollisten XOR-arvojen joukko, jotka voidaan saada valitsemalla mielivaltainen määrä lukuja (mahdollisesti $0$) luvuista $a_l, a_{l+1} \dots a_r$ ja ottamalla niiden kaikkien XOR. Toisin sanoen: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Tässä $\oplus$ tarkoittaa bittittäistä XOR-operaatiota. Esimerkiksi $4 \oplus 6 = 2$ ja $1 \oplus 2 = 3$.
• Selvitä, kuinka monta erilaista joukkoa $B(l, r)$ on olemassa kaikilla $1 \le l \le r \le n$.

Syöte

Tässä tehtävässä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$).

Seuraava rivi sisältää $n$ kokonaislukua $a_i$ ($0 \le a_i < 2^{32}$).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: erilaisten joukkojen $B(l, r)$ lukumäärän, eli $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Esimerkki

Syöte 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

Tuloste 1

4
10
12
36
46

Huomautus

Ensimmäisessä esimerkkitestitapauksessa kelvolliset joukot ovat: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.