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$、操作後の数列 $a$ の価値を $V_{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$ です。