Der NIT mag runde Schrauben. Er mag auch den Operator $\oplus$, weil er ihn an runde Schrauben erinnert, wobei $\oplus$ für die bitweise XOR-Operation (Bitwise-XOR) steht.

Definiere den Wert $V_a$ einer Folge $a_1, a_2, \cdots, a_n$ als $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Gegeben ist eine Folge $a_1, a_2, \cdots, a_n$. Du kannst die folgende Operation beliebig oft ausführen:

• Wähle einen Index $i$ ($1 \le i \le n$) und ändere $a_i$ in eine beliebige nicht-negative ganze Zahl; diese Operation kostet $C$.

Minimiere die Summe aus dem Wert der Folge und den durch die Operationen verursachten Kosten. Mit anderen Worten: Sei $p$ die Anzahl der ausgeführten Operationen und $V_{a'}$ der Wert von $a$ nach den Operationen, dann musst du $pC + V_{a'}$ minimieren.

Eingabe

Die Eingabe enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile zwei ganze Zahlen $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), die Länge der Folge und die Kosten für das Ausführen einer Operation.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), welche die Elemente der Folge darstellen.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall in einer Zeile eine ganze Zahl aus, den minimal möglichen Wert von $pC + V_{a'}$.

Beispiel

Eingabe

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

Ausgabe

14
24
29

Hinweis

Für den ersten Testfall besteht eine Möglichkeit zur Erreichung des Minimums darin, die Folge in $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$ zu ändern; die fettgedruckten Zahlen wurden geändert. Der endgültige Wert der Folge ist $2$, und es wurden $3$ Operationen durchgeführt; die Summe aus Wert und Kosten beträgt $2 + 3 \times 4 = 14$.

Für den zweiten Testfall besteht eine Möglichkeit zur Erreichung des Minimums darin, die Folge in $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$ zu ändern; der Endwert beträgt $12 + 2 \times 6 = 24$.