NIT lubi okrągłe śruby. Lubi też operator $\oplus$, ponieważ przypomina mu okrągłe śruby, gdzie $\oplus$ oznacza operację bitowego XOR (Bitwise-XOR).

Zdefiniujmy wartość $V_a$ ciągu $a_1, a_2, \cdots, a_n$ jako $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Dany jest ciąg $a_1, a_2, \cdots, a_n$. Możesz wykonać następującą operację dowolną liczbę razy:

• Wybierz indeks $i$ ($1 \le i \le n$) i zmień $a_i$ na dowolną nieujemną liczbę całkowitą; operacja ta ma koszt $C$.

Zminimalizuj sumę wartości ciągu oraz kosztu poniesionego na operacje. Innymi słowy, niech $p$ oznacza liczbę wykonanych operacji, a $V_{a'}$ wartość ciągu $a$ po wykonaniu operacji – musisz zminimalizować $pC + V_{a'}$.

Wejście

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera dwie liczby całkowite $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), oznaczające długość ciągu oraz koszt wykonania jednej operacji.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), reprezentujących elementy ciągu.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu jedną liczbę całkowitą – minimalną możliwą wartość $pC + V_{a'}$.

Przykład

Wejście

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

Wyjście

14
24
29

Uwaga

W pierwszym przypadku testowym jednym ze sposobów osiągnięcia minimum jest zmiana ciągu na $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; pogrubione liczby zostały zmienione. Końcowa wartość ciągu wynosi $2$, a wykonano $3$ operacje; łączna wartość + koszt wynosi $2 + 3 \times 4 = 14$.

W drugim przypadku testowym jednym ze sposobów osiągnięcia minimum jest zmiana ciągu na $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; końcowa wartość wynosi $12 + 2 \times 6 = 24$.