An và Bình vốn là bạn bè đồng trang lứa với nhau, và một hôm để hướng dẫn An tập tành với cờ vua, Bình đã đố An một bài toán trên bàn cờ vua như sau:

Cho bàn cờ vua có kích thước \(n*n\), với \(n\) là số nguyên dương, và các hàng được đánh số từ \(1\) đến \(n\).

Trong đó: Hàng \(1\) bao gồm một số quân tốt là các quân cờ của Bình và Hàng \(n\) bao gồm một số quân tốt là các quân cờ của An.

Bây giờ, Bình sẽ "án minh bất động" (tức là tất cả quân tốt của Bình đều đứng im) để An "tự do tung hành" đánh phá quân Bình, cụ thể như sau:

Mỗi lượt chơi, An có thể tự do di chuyển các quân tốt của mình cùng một lúc, và phải thoả mãn theo luật lệ của cờ vua quy định :

• Đó là quân tốt chỉ có thể di chuyển từ ô \((i,j)\) sang ô \((i-1,j)\) nếu ô đích đó không có bất kỳ quân tốt nào
• Quân tốt có thể từ ô thứ \((i,j)\) sang ô \((i-1,j-1)\) khi và chỉ khi ô này chứa quân tốt của đối phương.

Câu hỏi Bình đặt cho An như sau: Hỏi có tối đa bao nhiêu quân tốt của \(An\) có thể di chuyển đến xuống dòng 1.

Ví dụ 1: Giả sử, quân của An là màu trắng và quân của Bình là màu đen, thì ở ví dụ này, có tối đa \(4\) quân tốt có thể xuống được hàng \(1\)

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 50)\) - Thể hiện số testcase
• \(t\) block tiếp theo, mỗi block có dạng như sau:
• ++ Dòng thứ nhất chứa số nguyên dương \(n(2\le n\le 2*10^5)\) - Thể hiện kích thước bàn cờ vua
• ++ Dòng thứ hai chứa chứa xâu nhị phân gồm \(n\) kí tự, trong đó số \(0\) - tượng trưng cho ô đó trỗng rỗng, còn số \(1\) tượng trưng cho có quân tốt của Bình
• ++ Dòng thứ ba chứa chứa xâu nhị phân gồm \(n\) kí tự, trong đó số \(0\) - tượng trưng cho ô đó trỗng rỗng, còn số \(1\) tượng trưng cho có quân tốt của An

Output

• Ứng với testcase, hãy in kết quả ra màn hình.

Example

2
4
1111
1111
3
000
111
3
010
010

4
3
0