MAX-MEX Cut
Contest: Codeforces Global Round 16
Difficulty rating: 1000
Tags: bitmasks, constructive algorithms, dp, greedy

A binary string is a string that consists of characters $$$0$$$ and $$$1$$$. A bi-table is a table that has exactly two rows of equal length, each being a binary string.

Let $$$\operatorname{MEX}$$$ of a bi-table be the smallest digit among $$$0$$$, $$$1$$$, or $$$2$$$ that does not occur in the bi-table. For example, $$$\operatorname{MEX}$$$ for $$$\begin{bmatrix} 0011\\ 1010 \end{bmatrix}$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ occur in the bi-table at least once. $$$\operatorname{MEX}$$$ for $$$\begin{bmatrix} 111\\ 111 \end{bmatrix}$$$ is $$$0$$$, because $$$0$$$ and $$$2$$$ do not occur in the bi-table, and $$$0 < 2$$$.

You are given a bi-table with $$$n$$$ columns. You should cut it into any number of bi-tables (each consisting of consecutive columns) so that each column is in exactly one bi-table. It is possible to cut the bi-table into a single bi-table — the whole bi-table.

What is the maximal sum of $$$\operatorname{MEX}$$$ of all resulting bi-tables can be?

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of the description of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of columns in the bi-table.

Each of the next two lines contains a binary string of length $$$n$$$ — the rows of the bi-table.

It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case print a single integer — the maximal sum of $$$\operatorname{MEX}$$$ of all bi-tables that it is possible to get by cutting the given bi-table optimally.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case you can cut the bi-table as follows:

- $$$\begin{bmatrix} 0\\ 1 \end{bmatrix}$$$, its $$$\operatorname{MEX}$$$ is $$$2$$$.
- $$$\begin{bmatrix} 10\\ 10 \end{bmatrix}$$$, its $$$\operatorname{MEX}$$$ is $$$2$$$.
- $$$\begin{bmatrix} 1\\ 1 \end{bmatrix}$$$, its $$$\operatorname{MEX}$$$ is $$$0$$$.
- $$$\begin{bmatrix} 0\\ 1 \end{bmatrix}$$$, its $$$\operatorname{MEX}$$$ is $$$2$$$.
- $$$\begin{bmatrix} 0\\ 0 \end{bmatrix}$$$, its $$$\operatorname{MEX}$$$ is $$$1$$$.
- $$$\begin{bmatrix} 0\\ 0 \end{bmatrix}$$$, its $$$\operatorname{MEX}$$$ is $$$1$$$.

The sum of $$$\operatorname{MEX}$$$ is $$$8$$$.

Example input:
4
7
0101000
1101100
5
01100
10101
2
01
01
6
000000
111111

Example output:
8
8
2
12

Editorial:
Let's solve the same problem but for a string:
It's needed to cut a binary string into segments so that each its element is in exactly one segment and the sum of $$$\text{MEX}$$$ for all segments is maximal.
Initially we will say that the string is cut into segments of length 1. Then the answer is the number of zeroes in the string. After that the answer is increased every time we merge a segment of $$$0$$$ with a segment of $$$1$$$. Each such merge increases the answer by $$$1$$$. Let's make the merges greedily, maximizing the number of merges. Let's consider the first zero. If the previous element is a $$$1$$$, let's merge them and consider the next zero. Else, if the next element is a $$$1$$$, let's merge them and consider the next zero. Else, the next element is a zero and we should consider it instead of the current zero the same way. By doing so we get the answer as the number of zeroes + the number of merges.
Now let's solve the initial problem. We can cut out the columns that contain both $$$0$$$ and $$$1$$$, because their $$$\text{MEX}$$$ is already maximized and the answer will not become worse.
Now we solve the problem for all remaining bi-tables independently. Each their column consists either only of $$$0$$$ or only of $$$1$$$ so both rows are equal. We will solve the problem for one row of each remaining bi-table as mentioned before and then sum up the values to get the answer.