Сіз Ұмытылған Төбеде (Forgotten Hill) бір біртүрлі адамды танисыз. Бүгін сол біртүрлі адам сізден келесі есепті шығаруды сұрайды:

• Ақырлы $\mathbb{F}_2$ өрісі үстіндегі $32$-өлшемді $\mathbb{F}_2^{32}$ векторлық кеңістігі және оның ішіндегі $n$ элемент $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ берілген. $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$ мәнін табыңыз.

Біртүрлі адам кезінде Кішкентай Көгілдір Балыққа (Little Cyan Fish) өз есебін қалай шығару керектігін айтқан болатын. Алайда, оған қатысты естеліктерді біртүрлі адам бұлдыратып жіберген. Сондықтан Кішкентай Көгілдір Балық сіз осы біртүрлі адамның есебін шығара аласыз деп үміттенеді. Егер жоғарыдағы белгілеулер сізге таныс болмаса, Кішкентай Көгілдір Балық бұл есепті табиғи тілде былайша сипаттайды:

• Ұзындығы $n$ болатын теріс емес бүтін сандар тізбегі $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$) берілген.
• $B(l, r)$ мәнін $a_l, a_{l+1} \dots a_r$ ішінен кез келген мөлшердегі сандарды ($0$ сан болуы да мүмкін) таңдап, олардың барлығына XOR амалын қолдану арқылы алуға болатын барлық мүмкін XOR мәндерінің жиыны ретінде анықтайық. Басқаша айтқанда: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Мұндағы $\oplus$ разрядтық XOR амалын білдіреді. Мысалы, $4 \oplus 6 = 2$, $1 \oplus 2 = 3$.
• Барлық $1 \le l \le r \le n$ үшін қанша әртүрлі $B(l, r)$ жиыны бар екенін табыңыз.

Кіріс деректер

Бұл есепте бірнеше тест жиынтығы бар. Кіріс деректердің бірінші жолында тест жиынтықтарының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жиынтығы үшін бірінші жолда бір бүтін сан $n$ ($1 \le n \le 10^5$) берілген.

Келесі жолда $n$ бүтін сан $a_i$ ($0 \le a_i < 2^{32}$) берілген.

Барлық тест жиынтықтары бойынша $n$ қосындысы $10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін әртүрлі $B(l, r)$ жиындарының санын, яғни $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$ мәнін білдіретін бір бүтін саннан тұратын бір жолды шығарыңыз.

Мысал

Кіріс 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

Шығыс 1

4
10
12
36
46

Ескертпе

Бірінші мысалдағы тест жиынтығы үшін жарамды жиындар: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.