Lights Off

Bessie cần tắt tất cả đèn trong trang trại. Cô có hai xâu bit độ dài $N$ ($2\le N\le 20$): một biểu diễn trạng thái đèn và một biểu diễn công tắc.

Mỗi bước gồm:

1. Bật/tắt đúng một công tắc (toggle)
2. Với mỗi công tắc đang bật, toggle đèn tương ứng
3. Xoay vòng dãy công tắc sang phải một vị trí

Với mỗi cặp (đèn, công tắc), tìm số bước tối thiểu để tắt tất cả đèn.

Dữ liệu vào

• Dòng đầu: $T$ (số truy vấn, $1\le T\le 2\times {10}^5$) và $N$
• $T$ dòng tiếp: mỗi dòng gồm hai xâu bit độ dài $N$ (trạng thái đèn và công tắc)

Dữ liệu ra

Với mỗi truy vấn, in ra số bước tối thiểu.

Ràng buộc

• $2\le N\le 20$
• $1\le T\le 2\times {10}^5$
• Giới hạn thời gian: 4 giây

Ví dụ