Al NIT le gustan los tornillos redondos. También le gusta el operador $\oplus$ porque le recuerda a los tornillos redondos, donde $\oplus$ representa la operación XOR bit a bit (Bitwise-XOR).

Se define el valor $V_a$ de una secuencia $a_1, a_2, \cdots, a_n$ como $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Dada una secuencia $a_1, a_2, \cdots, a_n$, puedes realizar la siguiente operación un número arbitrario de veces:

• Seleccionar un índice $i$ ($1 \le i \le n$) y cambiar $a_i$ por cualquier entero no negativo; esta operación tiene un costo $C$.

Minimiza la suma del valor de la secuencia y el costo incurrido por las operaciones. En otras palabras, sea $p$ el número de operaciones realizadas y $V_{a'}$ el valor de $a$ después de las operaciones; debes minimizar $pC + V_{a'}$.

Entrada

La entrada contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 100$), el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene dos enteros $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), la longitud de la secuencia y el costo de realizar una operación.

La segunda línea contiene $n$ enteros $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), que representan los elementos de la secuencia.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime un entero en una línea: el valor mínimo posible de $pC + V_{a'}$.

Ejemplo

Entrada

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

Salida

14
24
29

Nota

Para el primer caso de prueba, una forma de lograr el mínimo es cambiar la secuencia a $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; los números en negrita son los modificados. El valor final de la secuencia es $2$ y se realizan $3$ operaciones; el valor total más el costo es $2 + 3 \times 4 = 14$.

Para el segundo caso de prueba, una forma de lograr el mínimo es cambiar la secuencia a $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; el valor final es $12 + 2 \times 6 = 24$.