Bessie muốn đi ngủ, nhưng đèn trong trang trại khiến cô không ngủ được. Làm thế nào để cô tắt chúng?

Bessie có hai chuỗi bit độ dài $N$ ($2\le N\le 20$), lần lượt biểu thị một dãy đèn và một dãy công tắc. Mỗi đèn đang bật (1) hoặc tắt (0). Mỗi công tắc đang hoạt động (1) hoặc không hoạt động (0).

Một bước gồm các thao tác sau theo đúng thứ tự:

1. Đảo trạng thái đúng một công tắc (cho nó hoạt động nếu đang không hoạt động, hoặc ngược lại).
2. Với mỗi công tắc đang hoạt động, đảo trạng thái đèn tương ứng (tắt nếu đang bật, hoặc ngược lại).
3. Dịch vòng các công tắc sang phải một vị trí. Cụ thể, nếu chuỗi bit biểu thị các công tắc ban đầu là $s_0s_1\dots s_{N-1}$ thì nó trở thành $s_{N-1}s_0s_1\dots s_{N-2}$.

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

Dữ liệu vào

Dòng đầu tiên chứa $T$ và $N$.

Mỗi dòng trong $T$ dòng tiếp theo chứa một cặp chuỗi bit độ dài $N$.

Dữ liệu ra

Với mỗi cặp, in số bước ít nhất cần thiết để tắt tất cả đèn.

Ví dụ

Dữ liệu vào 1

4 3
000 101
101 100
110 000
111 000

Dữ liệu ra 1

0
1
3
2

Ghi chú

• Trường hợp kiểm thử thứ nhất: tất cả đèn đã tắt.
• Trường hợp kiểm thử thứ hai: ta đảo trạng thái công tắc thứ ba ở bước đầu tiên.
• Trường hợp kiểm thử thứ ba: ta đảo trạng thái công tắc thứ nhất ở bước đầu tiên, công tắc thứ hai ở bước thứ hai và công tắc thứ hai lần nữa ở bước thứ ba.
• Trường hợp kiểm thử thứ tư: ta đảo trạng thái công tắc thứ nhất ở bước đầu tiên và công tắc thứ ba ở bước thứ hai.

Có thể chứng minh rằng trong mỗi trường hợp, đây là số bước ít nhất cần thiết.

Dữ liệu vào 2

1 10
1100010000 1000011000

Dữ liệu ra 2

2

Ghi chú

Có thể chứng minh rằng cần $2$ bước để tắt tất cả đèn.

• Ta đảo trạng thái công tắc thứ bảy ở bước đầu tiên, rồi lại đảo trạng thái nó ở bước thứ hai.

Nhiệm vụ con

• Đầu vào 3-5: $N \le 8$
• Đầu vào 6-13: $N\le 18$
• Đầu vào 14-20: không có ràng buộc bổ sung.

Tác giả bài toán: William Yue, Eric Yang và Benjamin Qi