你喺遺忘之丘（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）埋一齊，所能夠得到嘅所有可能異或值嘅集合。換句話講： $$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)$。

輸入格式

本題有多組測試數據。輸入嘅第一行包含一個整數 $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\}$。