คุณรู้จักคนประหลาดคนหนึ่งในเนินเขาที่ถูกลืม (Forgotten Hill) วันนี้คนประหลาดคนนี้ต้องการให้คุณแก้ปัญหาต่อไปนี้:

• กำหนดปริภูมิเวกเตอร์ $\mathbb{F}_2^{32}$ มิติ $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$
• จงหาว่าสำหรับทุก ๆ $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\}$