당신은 잊혀진 언덕(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)했을 때 얻을 수 있는 모든 가능한 XOR 값들의 집합으로 정의합니다. 다시 말해: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• 여기서 $\oplus$는 비트 XOR 연산을 나타냅니다. 예를 들어, $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\}$입니다.