你在遺忘之丘（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\}$。