Al NIT piacciono le viti rotonde. Gli piace anche l'operatore $\oplus$ perché gli ricorda le viti rotonde, dove $\oplus$ rappresenta l'operazione di XOR bit a bit (Bitwise-XOR).

Si definisce il valore $V_a$ di una sequenza $a_1, a_2, \cdots, a_n$ come $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$.

Data una sequenza $a_1, a_2, \cdots, a_n$, puoi eseguire la seguente operazione un numero arbitrario di volte:

• Seleziona un indice $i$ ($1 \le i \le n$) e modifica $a_i$ in un qualsiasi intero non negativo; questa operazione ha un costo $C$.

Minimizza la somma tra il valore della sequenza e il costo sostenuto per le operazioni. In altre parole, sia $p$ il numero di operazioni eseguite e $V_{a'}$ il valore di $a$ dopo le operazioni; devi minimizzare $pC + V_{a'}$.

Input

L'input contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 100$), il numero di casi di test.

Per ciascun caso di test, la prima riga contiene due interi $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$), la lunghezza della sequenza e il costo di esecuzione di un'operazione.

La seconda riga contiene $n$ interi $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$), che rappresentano gli elementi della sequenza.

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \times 10^5$.

Output

Per ciascun caso di test, stampa un intero su una riga, il minimo valore possibile di $pC + V_{a'}$.

Esempio

Input

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

Output

14
24
29

Note

Per il primo caso di test, un modo per ottenere il minimo è modificare la sequenza in $1, \mathbf{1}, \mathbf{1}, \mathbf{0}$; i numeri in grassetto sono quelli modificati. Il valore finale della sequenza è $2$ e vengono eseguite $3$ operazioni; il totale valore + costo è $2 + 3 \times 4 = 14$.

Per il secondo caso di test, un modo per ottenere il minimo è modificare la sequenza in $6, 6, 6, \mathbf{6}, \mathbf{6}, 6, 6, 6$; il valore finale è $12 + 2 \times 6 = 24$.