NIT 喜歡圓螺絲。他也喜歡 $\oplus$ 運算子，因為這讓他聯想到圓螺絲，其中 $\oplus$ 表示位元互斥或（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$。