Cô gái MTA thực sự thích ký hiệu nhị phân của các con số. Một buổi tối, cô ấy viết ra những con số ngẫu nhiên. Bởi một sự trùng hợp may mắn, tất cả những con số này đều là \(k\) bit, tức là đối với bất kỳ số \(a_i\) mà MTA đã viết thì \(0 \le a_i < 2^k\). Sau đó, cô ấy quan tâm đến câu hỏi: nếu cô ấy có thể thay đổi giá trị một số bit trong một số các số thành ngược lại, thì cần số lượng thao tác tối thiểu bao nhiêu, cô ấy sẽ có thể sắp xếp danh sách của mình theo thứ tự không giảm?

Input

Dòng đầu tiên chứa số nguyên \(t\) (\(1\le t \le 100\)) là số test. Tiếp theo là \(t\) nhóm dòng:

• Đầu tiên là số \(n, k\) (\(1\le n\le 100, 1\le k \le 30\)).
• \(n\) dòng tiếp theo mỗi dòng chứa một xâu nhị phân có độ dài \(k\).

Tổng \(n\) trong tất cả các test không vượt quá \(100\).

Output

• Đưa ra \(t\) dòng là kết quả của mỗi test.

Example

4
3 3
000
101
010
3 3
000
111
010
3 3
100
111
010
1 1
0

1
2
2
0