أنت تعرف شخصًا غريب الأطوار في تل النسيان (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$ إلى عملية XOR الثنائية (bitwise XOR). على سبيل المثال، $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\}$.