NIT дөңгелек бұрандаларды ұнатады. Сондай-ақ ол $\oplus$ операторын да ұнатады, өйткені бұл оған дөңгелек бұрандаларды еске салады, мұндағы $\oplus$ разрядтық XOR (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$ — сіз орындаған амалдар саны, ал $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$ болады.