You know an eccentric person in Forgotten Hill. Today, this eccentric person wants you to solve the following problem:

• Given the $32$-dimensional vector space $\mathbb{F}_2^{32}$ over the finite field $\mathbb{F}_2$ and $n$ elements $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ in it, find $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

The eccentric person once told Little Cyan Fish how to solve his problem. However, the relevant memories have been blurred by the eccentric person. Therefore, Little Cyan Fish hopes you can solve this eccentric person's problem. If you are unfamiliar with the notation above, Little Cyan Fish describes the problem in natural language as follows:

• Given a sequence of non-negative integers $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$) of length $n$.
• Define the value of $B(l, r)$ as the set of all possible XOR sums obtained by choosing any number of elements (possibly $0$) from $a_l, a_{l+1} \dots a_r$ and XORing them all together. In other words: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Here $\oplus$ denotes the bitwise XOR operation. For example, $4 \oplus 6 = 2$ and $1 \oplus 2 = 3$.
• Find how many distinct sets $B(l, r)$ there are over all $1 \le l \le r \le n$.

Input

There are multiple test cases in this problem. The first line of input contains an integer $T$ ($1 \le T$), denoting the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \le n \le 10^5$).

The next line contains $n$ integers $a_i$ ($0 \le a_i < 2^{32}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single line containing an integer denoting the number of distinct sets $B(l, r)$, i.e., $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Example

Input 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

Output 1

4
10
12
36
46

Note

For the first sample test case, the valid sets are: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.