NIT thích những chiếc ốc vít tròn. Anh ấy cũng thích toán tử $\oplus$ vì nó gợi cho anh nhớ đến những chiếc ốc vít tròn, trong đó $\oplus$ biểu thị phép toán XOR theo bit (Bitwise-XOR).

Định nghĩa giá trị $V_a$ của một dãy $a_1, a_2, \cdots, a_n$ là $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Cho một dãy $a_1, a_2, \cdots, a_n$, bạn có thể thực hiện thao tác sau số lần tùy ý:

• Chọn một chỉ số $i$ ($1 \le i \le n$), đổi $a_i$ thành một số nguyên không âm bất kỳ; thao tác này có chi phí là $C$.

Hãy cực tiểu hóa tổng giá trị của dãy và chi phí phát sinh từ các thao tác. Nói cách khác, gọi $p$ là số thao tác bạn đã thực hiện, và $V_{a'}$ là giá trị của dãy $a$ sau các thao tác, bạn cần cực tiểu hóa $pC + V_{a'}$.

Dữ liệu

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$) là số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa hai số nguyên $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), lần lượt là độ dài của dãy và chi phí thực hiện một thao tác.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), biểu thị các phần tử trong dãy.

Dữ liệu đảm bảo tổng của $n$ trên tất cả các bộ test không vượt quá $2 \times 10^5$.

Kết quả

Với mỗi bộ test, in ra một số nguyên trên một dòng là giá trị nhỏ nhất có thể của $pC + V_{a'}$.

Ví dụ

Dữ liệu

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

Kết quả

14
24
29

Giải thích

Ở bộ test đầu tiên, một cách để đạt giá trị nhỏ nhất là đổi dãy thành $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; các số in đậm là những số đã được thay đổi. Giá trị của dãy cuối cùng là $2$, và có $3$ thao tác được thực hiện; tổng giá trị + chi phí là $2 + 3 \times 4 = 14$.

Ở bộ test thứ hai, một cách để đạt giá trị nhỏ nhất là đổi dãy thành $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; giá trị cuối cùng là $12 + 2 \times 6 = 24$.