NIT ชอบสกรูหัวกลม เขายังชอบตัวดำเนินการ $\oplus$ เพราะมันทำให้เขานึกถึงสกรูหัวกลม โดยที่ $\oplus$ แทนการดำเนินการ Bitwise-XOR

นิยามค่า $V_a$ ของลำดับ $a_1, a_2, \cdots, a_n$ เป็น $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$

กำหนดลำดับ $a_1, a_2, \cdots, a_n$ คุณสามารถดำเนินการต่อไปนี้กี่ครั้งก็ได้:

• เลือกดัชนี $i$ ($1 \le i \le n$) แล้วเปลี่ยนค่า $a_i$ เป็นจำนวนเต็มไม่ลบใดๆ การดำเนินการนี้มีค่าใช้จ่าย $C$

จงทำให้ผลรวมของค่าของลำดับและค่าใช้จ่ายที่เกิดจากการดำเนินการมีค่าน้อยที่สุด กล่าวอีกนัยหนึ่ง ให้ $p$ เป็นจำนวนการดำเนินการที่คุณทำ และ $V_{a'}$ เป็นค่าของลำดับ $a$ หลังจากการดำเนินการ คุณต้องทำให้ค่า $pC + V_{a'}$ น้อยที่สุด

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยหลายชุดทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 100$) แทนจำนวนชุดทดสอบ

สำหรับแต่ละชุดทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$) แทนความยาวของลำดับและค่าใช้จ่ายในการดำเนินการหนึ่งครั้ง

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$) แทนสมาชิกในลำดับ

รับประกันว่าผลรวมของ $n$ จากทุกชุดทดสอบไม่เกิน $2 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบ ให้พิมพ์จำนวนเต็มหนึ่งจำนวนในหนึ่งบรรทัด คือค่าน้อยที่สุดที่เป็นไปได้ของ $pC + V_{a'}$

ตัวอย่าง

ข้อมูลนำเข้า

3
4 4
1 4 5 6
8 6
6 6 6 1 1 6 6 6
6 7
1 7 2 6 3 5

ข้อมูลส่งออก

14
24
29

หมายเหตุ

สำหรับชุดทดสอบแรก วิธีหนึ่งที่จะได้ค่าน้อยที่สุดคือเปลี่ยนลำดับเป็น $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$ โดยตัวเลขตัวหนาคือตัวที่ถูกเปลี่ยน ค่าของลำดับสุดท้ายคือ $2$ และมีการดำเนินการ $3$ ครั้ง ผลรวมของค่าและค่าใช้จ่ายคือ $2 + 3 \times 4 = 14$

สำหรับชุดทดสอบที่สอง วิธีหนึ่งที่จะได้ค่าน้อยที่สุดคือเปลี่ยนลำดับเป็น $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$ ค่าสุดท้ายคือ $12 + 2 \times 6 = 24$