Anda mengenal seseorang yang eksentrik di Forgotten Hill. Hari ini, orang eksentrik ini ingin Anda menyelesaikan masalah berikut:

• Diberikan ruang vektor berdimensi $32$, yaitu $\mathbb{F}_2^{32}$, atas lapangan hingga $\mathbb{F}_2$ beserta $n$ elemen $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ di dalamnya. Carilah $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Orang eksentrik itu pernah memberi tahu Ikan Sian Kecil (Little Cyan Fish) cara menyelesaikan masalahnya. Namun, ingatan terkait telah dikaburkan oleh orang eksentrik tersebut. Oleh karena itu, Ikan Sian Kecil berharap Anda dapat menyelesaikan masalah orang eksentrik ini. Jika Anda tidak terbiasa dengan notasi di atas, Ikan Sian Kecil menjelaskan masalah tersebut dalam bahasa alami sebagai berikut:

• Diberikan sebuah barisan bilangan bulat tak negatif sepanjang $n$, yaitu $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Definisikan nilai $B(l, r)$ sebagai himpunan semua kemungkinan nilai XOR yang diperoleh dengan memilih sejumlah bilangan berapa pun (bisa saja $0$ bilangan) dari $a_l, a_{l+1} \dots a_r$ lalu melakukan operasi XOR pada semuanya. Dengan kata lain: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Di sini $\oplus$ menyatakan operasi bitwise XOR. Sebagai contoh, $4 \oplus 6 = 2$ dan $1 \oplus 2 = 3$.
• Carilah berapa banyak himpunan $B(l, r)$ yang berbeda untuk semua $1 \le l \le r \le n$.

Format Masukan

Terdapat beberapa kasus uji dalam soal ini. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$).

Baris berikutnya berisi $n$ bilangan bulat $a_i$ ($0 \le a_i < 2^{32}$).

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $10^5$.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat yang menyatakan banyaknya himpunan $B(l, r)$ yang berbeda, yaitu $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Contoh

Masukan 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

Keluaran 1

4
10
12
36
46

Catatan

Untuk kasus uji contoh pertama, himpunan yang valid meliputi: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.