אתה מכיר אדם תמהוני בגבעת השכחה (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 על סיביות. לדוגמה, $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\}$.