NIT gillar runda skruvar. Han gillar också operatorn $\oplus$ eftersom den påminner honom om runda skruvar, där $\oplus$ representerar bitvis XOR (Bitwise-XOR).

Definiera värdet $V_a$ för en talföljd $a_1, a_2, \cdots, a_n$ som $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Givet en talföljd $a_1, a_2, \cdots, a_n$ kan du utföra följande operation valfritt antal gånger:

• Välj ett index $i$ ($1 \le i \le n$) och ändra $a_i$ till ett godtyckligt icke-negativt heltal; denna operation har en kostnad $C$.

Minimera summan av talföljdens värde och kostnaden som uppstår av operationerna. Med andra ord, låt $p$ vara antalet operationer du utfört och $V_{a'}$ vara värdet av $a$ efter operationerna; då ska du minimera $pC + V_{a'}$.

Indata

Indatan innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 100$), antalet testfall.

För varje testfall innehåller den första raden två heltal $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), längden på talföljden och kostnaden för att utföra en operation.

Den andra raden innehåller $n$ heltal $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), som representerar elementen i talföljden.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut ett heltal på en rad, det minsta möjliga värdet av $pC + V_{a'}$.

Exempel

Indata

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

Utdata

14
24
29

Förklaring

För det första testfallet är ett sätt att uppnå minimum att ändra talföljden till $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; de fetstilta talen är de ändrade. Det slutliga värdet på talföljden är $2$, och $3$ operationer görs; totalt värde + kostnad är $2 + 3 \times 4 = 14$.

För det andra testfallet är ett sätt att uppnå minimum att ändra talföljden till $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; det slutliga värdet är $12 + 2 \times 6 = 24$.