Ви знайомі з одним диваком на Забутому Пагорбі (Forgotten Hill). Сьогодні цей дивак хоче, щоб ви розв'язали таку задачу:

• Дано $32$-вимірний векторний простір $\mathbb{F}_2^{32}$ над скінченним полем $\mathbb{F}_2$ та $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)$ як множину всіх можливих значень виключного АБО (XOR), які можна отримати, вибравши довільну кількість чисел (можливо, $0$) із $a_l, a_{l+1} \dots a_r$ і застосувавши до всіх них операцію 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$.
• Знайдіть, скільки існує різних множин $B(l, r)$ для всіх $1 \le l \le r \le n$.

Вхідні дані

У цій задачі декілька наборів тестових даних. Перший рядок вхідних даних містить одне ціле число $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\}$.