Giải bài trực tuyến

Pirate đang trên chuyến tàu sẽ đưa anh đến với hòn đảo mà anh hằng mong ước với dừa xanh, cát trắng và biển ngọc. Tuy nhiên, trước tiên anh phải tìm ra cách để đốt cháy hết khoảng thời gian ngồi bó gối trên khoang tàu. Những con số lại ập vào suy nghĩ của Pirate...

Pirate nghĩ ra N số nguyên dương ở hệ nhị phân, mỗi số gồm L bit. Anh ta nhận thấy rằng giữa các số có một mối quan hệ rất dễ nhìn thấy, là việc chúng giống nhau ở một bit tại vị trí nào đó. Pirate muốn phân nhóm N số trên theo tính chất này, cụ thể là:

• Mỗi số phải thuộc vào duy nhất một nhóm.
• Mỗi nhóm gồm các số giống nhau ở bit K (các bit được đánh số từ 1 đến L, 0 < K ≤ L). Ta gọi đó là nhóm bit-K.
• Không thể có hai nhóm bit-K cùng tồn tại. Tức là, nếu có nhóm bit-K mà bit giống nhau của các số là bit 1 thì không thể có một nhóm bit-K khác mà bit giống nhau là bit 0.

Tuy nhiên, việc phân nhóm đơn thuần như vậy quá dễ dàng đối với Pirate. Để mất thêm thời gian, anh ấy muốn tính xem có thể phân ra được ít nhất bao nhiêu nhóm từ N số trên.

Input

Dòng đầu tiên ghi số nguyên T là số bộ test.

T nhóm dòng sau, mỗi nhóm gồm hai dòng thể hiện một bộ test với cấu trúc như sau:

• Dòng thứ nhất ghi hai số nguyên dương N và L.
• N dòng tiếp theo mỗi dòng ghi một số nguyên dương. 

Output

Output gồm T dòng, mỗi dòng ghi ra số lượng nhóm ít nhất có thể phân chia được ứng với bộ test tương ứng.

Chấm điểm

Trong quá trình thi, bài của bạn sẽ được chấm với 40% test. Điểm số mà bạn nhận được thể hiện phần trăm test mà bạn giải đúng trong các test đó (trên thang điểm 100).

Example

Input:

1
4 3
1
6
7
4
Output:
2

Giải thích

Biểu diễn nhị phân của các số trên lần lượt là: 001, 110, 111, 100. Ta phân chia các số trên thành hai nhóm: nhóm bit-2 gồm (001, 100} và nhóm bit-3 gồm {110, 111}. 

Giới hạn

• 1 ≤ T ≤ 4
• 1 ≤ N ≤ 50.
• 2 ≤ L ≤ 20. Trong 40% số test, 2 ≤ L ≤ 8.
• Các số trong Input là số nguyên dương không vượt quá 2^L - 1.
• Dữ liệu đảm bảo có cách chia nhóm thỏa mãn đề bài.