NIT любить круглі шурупи. Йому також подобається оператор $\oplus$, бо він нагадує йому круглі шурупи, де $\oplus$ позначає операцію побітового виключного АБО (Bitwise-XOR).

Визначимо значення $V_a$ послідовності $a_1, a_2, \cdots, a_n$ як $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$.