あなたは 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 に自分の問題の解き方を教えたことがありました。しかし、関連する記憶は変人によって曖昧にされてしまいました。そのため、Little Cyan Fish はあなたにこの変人の問題を解いてほしいと願っています。上記の記号に馴染みがない場合のために、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$ はビットごとの排他的論理和演算を表す。例えば、$4 \oplus 6 = 2$、$1 \oplus 2 = 3$ である。
• すべての $1 \le l \le r \le n$ に対して、相異なる集合 $B(l, r)$ がいくつあるかを求めよ。

入力

この問題には複数のテストケースが含まれる。入力の 1 行目には、テストケースの個数を表す整数 $T$（$1 \le T$）が与えられる。

各テストケースについて、1 行目には整数 $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 行に出力せよ。

入出力例

入力 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

注記

1 番目のサンプルテストケースにおいて、条件を満たす集合は $\{0, 1\}$、$\{0, 2\}$、$\{0, 3\}$、$\{0, 1, 2, 3\}$ である。