NIT는 둥근 나사를 좋아합니다. 또한 둥근 나사를 떠올리게 하는 $\oplus$ 연산자도 좋아하는데, 여기서 $\oplus$는 비트별 배타적 논리합(Bitwise-XOR) 연산을 나타냅니다.

수열 $a_1, a_2, \cdots, a_n$의 가치 $V_a$를 $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$, 연산 후 수열 $a$의 가치를 $V_{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$입니다.