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