Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường.

Bessie muốn đi ngủ, nhưng ánh sáng từ trang trại khiến cô ấy không thể chợp mắt. Làm thế nào để cô ấy có thể tắt hết đèn?

Bessie có hai chuỗi nhị phân độ dài \(N\) (\(2 \le N \le 20)\), lần lượt đại diện cho trạng thái của các đèn và các công tắc. Mỗi đèn có thể đang bật (1) hoặc tắt (0). Mỗi công tắc có thể đang hoạt động (1) hoặc không hoạt động (0).

Một thao tác bao gồm các bước sau:

1. Thay đổi trạng thái của đúng một công tắc (nếu đang không hoạt động thì bật lên, và ngược lại).
2. Đối với mỗi công tắc đang hoạt động, thay đổi trạng thái của đèn tương ứng (nếu đèn đang bật thì tắt, và ngược lại).
3. Xoay vòng các công tắc sang phải một vị trí. Cụ thể, nếu chuỗi nhị phân ban đầu của các công tắc là \(s_0s_1\dots s_{N-1}\) thì sau khi xoay sẽ trở thành \(s_{N-1}s_0s_1\dots s_{N-2}\).

Với \(T\) (\(1 \le T \le 2 \cdot 10^5\)) trường hợp cho bài toán trên, hãy tính số thao tác tối thiểu để tắt hết tất cả các đèn.

Input

• Dòng đầu tiên chứa \(T\) và \(N\).
• \(T\) dòng tiếp theo, mỗi dòng chứa một cặp chuỗi nhị phân độ dài \(N\).

Output

• Với mỗi cặp chuỗi, in ra số lượt thao tác tối thiểu để tắt hết các đèn.

Scoring

• Subtask \(1\): \(N \le 8\)
• Subtask \(2\): \(N \le 18\)
• Subtask \(3\): Không có ràng buộc nào khác.

4 3
000 101
101 100
110 000
111 000

0
1
3
2

1 10
1100010000 1000011000

2