Masala #0207

Sizga $n$ ta elementdan iborat $A(A_1, A_2, \dots, A_n)$ to’plam berilgan.

$F(x) = \displaystyle\sum_{i=1}^n A_i ∧ x$

Bu yerda $F(x)$ funksiya $A$ to’plamning barcha elementlari bilan $x$ orasida bitwise and operatorini qo’llab hosil bo’lgan qiymatlarning umumiy summasini hisoblab beradi.

Sizning vazifangiz $F(x)$ funksiyadan qaytadigan qiymat eng katta bo’ladigan, ikkilik ifodalanishida jami $L$ ta 1 ishtirok etadigan $x$ lar sonini topishdan iborat!

Kirish faylining dastlabki satrida bitta butun son, $T \space (1 \le T \le 1000)$ testlar soni kiritiladi. Keyingi qatordan boshlab har bir test uchun alohida ikkita qatorning birinchi satrida ikkita butun son, $n \space (1 \le N \le 20000)$ va $L \space (1 \le L \le 30)$, mos ravishda $A$ to’plam elementlar soni va $x$ ning ikkilik ko’rinishidagi 1 lar soni, ikkinchi satrida esa $n$ ta butun son, $A (1 \le A_i \le 10^9)$ to’plam elementlari kiritiladi.

Barcha testlardagi $N$ lar yig’indisi 200000 dan oshmasligi kafolatlanadi.

Har bir test uchun alohida qatorda $F(x)$ funksiyasidan eng katta qiymat qaytaradigan $x$ ning bo’lishi mumkin bo’lgan qiymatlar sonini chop eting, agar bunday sonlar cheksiz bo’lsa o’rniga -1 chop eting.