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$.