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$。