يحب NIT البراغي المستديرة. كما يحب المعامل $\oplus$ لأنه يذكره بالبراغي المستديرة، حيث يمثل $\oplus$ عملية XOR على مستوى البتات (Bitwise-XOR).

نعرّف قيمة المتتالية $a_1, a_2, \cdots, a_n$، والتي نرمز لها بـ $V_a$، على أنها $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$.