Cắt bi-bảng MAX-MEX

Một bi-bảng là một bảng gồm đúng hai hàng có độ dài bằng nhau, mỗi hàng là một xâu nhị phân (chỉ gồm các ký tự 0 và 1).

Với một bi-bảng, định nghĩa $MEX$ của nó là số nhỏ nhất trong tập $\{0,1,2\}$ không xuất hiện trong bi-bảng đó. Ví dụ, $MEX$ của bi-bảng

$$\left[\begin{array}{c}0011\\ 1010\end{array}\right]$$

bằng $2$, vì cả $0$ và $1$ đều xuất hiện. $MEX$ của bi-bảng

$$\left[\begin{array}{c}111\\ 111\end{array}\right]$$

bằng $0$, vì $0$ không xuất hiện (và $0<2$).

Cho một bi-bảng có $n$ cột. Bạn cần cắt nó thành một số bi-bảng con (mỗi bi-bảng con gồm các cột liên tiếp) sao cho mỗi cột thuộc về đúng một bi-bảng con. Cho phép giữ nguyên cả bảng làm một bi-bảng con duy nhất.

Hãy tính tổng $MEX$ lớn nhất của các bi-bảng con thu được.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ($1\le t\le {10}^4$) — số bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng đầu chứa số nguyên $n$ ($1\le n\le {10}^5$) — số cột của bi-bảng.
• Hai dòng tiếp theo, mỗi dòng chứa một xâu nhị phân độ dài $n$ — hai hàng của bi-bảng.

Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên — tổng $MEX$ lớn nhất có thể đạt được.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le {10}^5$
• Tổng $n\le {10}^5$

Ví dụ