NIT pitää pyöreistä ruuveista. Hän pitää myös $\oplus$-operaattorista, koska se muistuttaa häntä pyöreistä ruuveista, missä $\oplus$ tarkoittaa bittittäistä XOR-operaatiota (Bitwise-XOR).

Määritellään lukujonon $a_1, a_2, \cdots, a_n$ arvo $V_a$ kaavalla $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Annettuna on lukujono $a_1, a_2, \cdots, a_n$. Voit suorittaa seuraavan operaation mielivaltaisen monta kertaa:

• Valitse indeksi $i$ ($1 \le i \le n$) ja muuta $a_i$ miksi tahansa epänegatiiviseksi kokonaisluvuksi; tämän operaation hinta on $C$.

Minimoi lukujonon arvon ja operaatioista aiheutuvien kustannusten summa. Toisin sanoen, olkoon $p$ suorittamiesi operaatioiden lukumäärä ja $V_{a'}$ jonon $a$ arvo operaatioiden jälkeen, jolloin sinun tulee minimoida $pC + V_{a'}$.

Syöte

Syöte sisältää useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kaksi kokonaislukua $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), lukujonon pituuden ja yhden operaation suorittamisen hinnan.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), jotka kuvaavat lukujonon alkioita.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yhdellä rivillä kokonaisluku, lausekkeen $pC + V_{a'}$ pienin mahdollinen arvo.

Esimerkki

Syöte

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

Tuloste

14
24
29

Huomautus

Ensimmäisessä testitapauksessa yksi tapa saavuttaa minimi on muuttaa lukujonoksi $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; lihavoidut luvut ovat muutettuja. Lopullisen lukujonon arvo on $2$, ja tehdään $3$ operaatiota; kokonaisarvo + kustannus on $2 + 3 \times 4 = 14$.

Toisessa testitapauksessa yksi tapa saavuttaa minimi on muuttaa lukujonoksi $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; lopullinen arvo on $12 + 2 \times 6 = 24$.