NIT liker runde skruer. Han liker også operatoren $\oplus$ fordi den minner ham om runde skruer, der $\oplus$ representerer bitvis XOR (Bitwise-XOR).

Definer verdien $V_a$ til en følge $a_1, a_2, \cdots, a_n$ som $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Gitt en følge $a_1, a_2, \cdots, a_n$, kan du utføre følgende operasjon et vilkårlig antall ganger:

• Velg en indeks $i$ ($1 \le i \le n$), og endre $a_i$ til et hvilket som helst ikke-negativt heltall; denne operasjonen har en kostnad $C$.

Minimer summen av verdien til følgen og kostnaden som påløper ved operasjonene. Med andre ord, la $p$ være antall operasjoner du utførte, og $V_{a'}$ være verdien av $a$ etter operasjonene; da må du minimere $pC + V_{a'}$.

Inndata

Inndataene inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 100$), antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen to heltall $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), lengden på følgen og kostnaden for å utføre én operasjon.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), som representerer elementene i følgen.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut et heltall på én linje, den minste mulige verdien av $pC + V_{a'}$.

Eksempel

Inndata

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

Utdata

14
24
29

Forklaring

For det første testtilfellet er én måte å oppnå minimum på å endre følgen til $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; de uthevede tallene er de som er endret. Den endelige følgeverdien er $2$, og $3$ operasjoner utføres; total verdi + kostnad er $2 + 3 \times 4 = 14$.

For det andre testtilfellet er én måte å oppnå minimum på å endre følgen til $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; den endelige verdien er $12 + 2 \times 6 = 24$.