NIT heldur upp á kringlóttar skrúfur. Hann heldur líka upp á virkjann $\oplus$ vegna þess að hann minnir hann á kringlóttar skrúfur, þar sem $\oplus$ táknar bitbundna XOR-aðgerð (Bitwise-XOR).

Skilgreinum gildið $V_a$ á runu $a_1, a_2, \cdots, a_n$ sem $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Gefin er runa $a_1, a_2, \cdots, a_n$ og þú getur framkvæmt eftirfarandi aðgerð eins oft og þú vilt:

• Veldu vísi $i$ ($1 \le i \le n$) og breyttu $a_i$ í hvaða óneikvæða heiltölu sem er; þessi aðgerð kostar $C$.

Lágmarkaðu summu gildis rununnar og kostnaðarins sem hlýst af aðgerðunum. Með öðrum orðum, látum $p$ vera fjölda aðgerða sem þú framkvæmdir og $V_{a'}$ vera gildi $a$ eftir aðgerðirnar; þá þarftu að lágmarka $pC + V_{a'}$.

Inntak

Inntakið inniheldur mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 100$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan tvær heiltölur $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), lengd rununnar og kostnaðinn við að framkvæma eina aðgerð.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), sem tákna stökin í rununni.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta heiltölu í einni línu, minnsta mögulega gildið á $pC + V_{a'}$.

Dæmi

Inntak

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

Úttak

14
24
29

Athugasemd

Í fyrsta prófunartilvikinu er ein leið til að ná lágmarkinu að breyta rununni í $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; feitletruðu tölurnar eru þær sem var breytt. Lokagildi rununnar er $2$ og $3$ aðgerðir eru framkvæmdar; heildargildi + kostnaður er $2 + 3 \times 4 = 14$.

Í öðru prófunartilvikinu er ein leið til að ná lágmarkinu að breyta rununni í $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; lokagildið er $12 + 2 \times 6 = 24$.