NIT menyukai sekrup bulat. Ia juga menyukai operator $\oplus$ karena mengingatkannya pada sekrup bulat, di mana $\oplus$ menyatakan operasi Bitwise-XOR.

Definisikan nilai $V_a$ dari sebuah barisan $a_1, a_2, \cdots, a_n$ sebagai $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Diberikan sebuah barisan $a_1, a_2, \cdots, a_n$, Anda dapat melakukan operasi berikut sebanyak berapa kali pun:

• Pilih sebuah indeks $i$ ($1 \le i \le n$), ubah $a_i$ menjadi bilangan bulat non-negatif berapa pun; operasi ini memiliki biaya $C$.

Minimumkan jumlah dari nilai barisan dan biaya yang ditimbulkan oleh operasi. Dengan kata lain, misalkan $p$ adalah banyaknya operasi yang Anda lakukan, dan $V_{a'}$ adalah nilai dari $a$ setelah operasi, maka Anda perlu meminimumkan $pC + V_{a'}$.

Masukan

Masukan terdiri atas beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$), yaitu banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), yaitu panjang barisan dan biaya untuk melakukan satu operasi.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), yang menyatakan elemen-elemen dalam barisan.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, cetak sebuah bilangan bulat dalam satu baris, yaitu nilai minimum yang mungkin dari $pC + V_{a'}$.

Contoh

Masukan

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

Keluaran

14
24
29

Catatan

Untuk kasus uji pertama, salah satu cara untuk mencapai minimum adalah mengubah barisan menjadi $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; angka-angka tebal adalah yang diubah. Nilai akhir barisan adalah $2$, dan $3$ operasi dilakukan; total nilai + biaya adalah $2 + 3 \times 4 = 14$.

Untuk kasus uji kedua, salah satu cara untuk mencapai minimum adalah mengubah barisan menjadi $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; nilai akhirnya adalah $12 + 2 \times 6 = 24$.