NIT אוהב ברגים עגולים. הוא גם אוהב את האופרטור $\oplus$ משום שהוא מזכיר לו ברגים עגולים, כאשר $\oplus$ מייצג את פעולת ה-XOR הסיביתית (Bitwise-XOR).

נגדיר את הערך $V_a$ של סדרה $a_1, a_2, \cdots, a_n$ להיות $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$.