Bạn quen một người kỳ quặc ở Đồi Lãng Quên (Forgotten Hill). Hôm nay, người kỳ quặc này muốn bạn giải quyết bài toán sau:

• Cho không gian vectơ $32$ chiều $\mathbb{F}_2^{32}$ trên trường hữu hạn $\mathbb{F}_2$ và $n$ phần tử $a_1, a_2, \dots, a_n \in \mathbb{F}_2^{32}$ trong đó. Hãy tìm $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Người kỳ quặc từng nói cho Cá Xanh Nhỏ (Little Cyan Fish) cách giải bài toán của ông ta. Tuy nhiên, những ký ức liên quan đã bị người kỳ quặc làm mờ đi. Vì vậy, Cá Xanh Nhỏ hy vọng bạn có thể giải được bài toán của người kỳ quặc này. Nếu bạn không quen với các ký hiệu trên, Cá Xanh Nhỏ mô tả bài toán bằng ngôn ngữ tự nhiên như sau:

• Cho một dãy số nguyên không âm độ dài $n$ là $a_1, a_2 \dots a_n$ ($0 \le a_i < 2^{32}$).
• Định nghĩa giá trị của $B(l, r)$ là tập hợp tất cả các giá trị XOR có thể nhận được bằng cách chọn một số lượng phần tử tùy ý (có thể là $0$ phần tử) từ $a_l, a_{l+1} \dots a_r$ và XOR tất cả chúng lại với nhau. Nói cách khác: $$B(l, r) = \left\{ \bigoplus_{i=l}^r c_i a_i \;\middle|\; c_i \in \{0, 1\} \right\}$$
• Trong đó $\oplus$ biểu thị phép toán XOR theo bit. Ví dụ: $4 \oplus 6 = 2$, $1 \oplus 2 = 3$.
• Hãy tìm xem với mọi $1 \le l \le r \le n$, có bao nhiêu tập hợp $B(l, r)$ phân biệt.

Dữ liệu vào

Bài toán này có nhiều bộ test. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T$), biểu thị số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$).

Dòng tiếp theo chứa $n$ số nguyên $a_i$ ($0 \le a_i < 2^{32}$).

Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ test không vượt quá $10^5$.

Kết quả

Với mỗi bộ test, in ra một dòng chứa một số nguyên biểu thị số lượng tập hợp $B(l, r)$ phân biệt, tức là $|\{\text{span}_{\mathbb{F}_2}\{a_l, a_{l+1}, \dots, a_r\} \mid 1 \le l \le r \le n\}|$.

Ví dụ

Đầu vào 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

Đầu ra 1

4
10
12
36
46

Giải thích

Đối với bộ test ví dụ đầu tiên, các tập hợp hợp lệ bao gồm: $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 1, 2, 3\}$.