Znasz pewnego dziwaka w Forgotten Hill. Dziś ten dziwak chce, abyś rozwiązał następujące zadanie:

• Dana jest $32$-wymiarowa przestrzeń wektorowa $\mathbb{F}_2^{32}$ nad ciałem skończonym $\mathbb{F}_2$ oraz $n$ jej elementów $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$. Wyznacz $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Dziwak powiedział kiedyś Małej Cyjanowej Rybce (Little Cyan Fish), jak rozwiązać jego zadanie. Jednak związane z tym wspomnienia zostały przez dziwaka zamazane. Dlatego Mała Cyjanowa Rybka ma nadzieję, że zdołasz rozwiązać zadanie tego dziwaka. Jeśli nie znasz powyższej notacji, Mała Cyjanowa Rybka opisuje to zadanie w języku naturalnym następująco:

• Dany jest ciąg nieujemnych liczb całkowitych o długości $n$: $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Wartość $B(l, r)$ definiujemy jako zbiór wszystkich możliwych wartości XOR, które można otrzymać, wybierając dowolną liczbę elementów (być może $0$) spośród $a_l, a_{l+1} \dots a_r$ i wykonując na nich wszystkich operację XOR. Innymi słowy: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Gdzie $\oplus$ oznacza bitową operację XOR. Na przykład $4 \oplus 6 = 2$ oraz $1 \oplus 2 = 3$.
• Wyznacz, ile jest istotnie różnych zbiorów $B(l, r)$ dla wszystkich $1 \le l \le r \le n$.

Wejście

W tym zadaniu występuje wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^5$).

Kolejny wiersz zawiera $n$ liczb całkowitych $a_i$ ($0 \le a_i < 2^{32}$).

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą oznaczającą liczbę istotnie różnych zbiorów $B(l, r)$, czyli $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Przykład

Wejście 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

Wyjście 1

4
10
12
36
46

Uwaga

Dla pierwszego przykładowego przypadku testowego poprawne zbiory to: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.