C. MAX-MEX разрез
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бинарная строка — это строка, состоящая из символов $$$0$$$ и $$$1$$$. Би-таблица — это таблица, состоящая из ровно двух бинарных строк одинаковой длины.

Определим $$$\operatorname{MEX}$$$ би-таблицы как наименьшую из цифр $$$0$$$, $$$1$$$ или $$$2$$$, которая не встречается в этой би-таблице. Например, $$$\operatorname{MEX}$$$ для $$$\begin{bmatrix} 0011\\ 1010 \end{bmatrix}$$$ — это $$$2$$$, потому что $$$0$$$ и $$$1$$$ встречаются хотя бы один раз. $$$\operatorname{MEX}$$$ для $$$\begin{bmatrix} 111\\ 111 \end{bmatrix}$$$ — это $$$0$$$, потому что $$$0$$$ и $$$2$$$ не встречаются ни разу, и $$$0 < 2$$$.

Дана би-таблица с $$$n$$$ столбцами. Необходимо разбить её на произвольное количество би-таблиц (каждая состоит из последовательных столбцов) так, чтобы каждый её столбец принадлежал ровно одной би-таблице. Би-таблицу разрешается разбить на одну би-таблицу — её саму.

Какую максимальную сумму $$$\operatorname{MEX}$$$ всех полученных би-таблиц можно получить?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество столбцов в би-таблице.

Каждая из следующих двух строк содержит бинарную строку длины $$$n$$$  — это строки би-таблицы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — наибольшую сумму $$$\operatorname{MEX}$$$, которую можно получить, разбив би-таблицу оптимально.

Пример
Входные данные
4
7
0101000
1101100
5
01100
10101
2
01
01
6
000000
111111
Выходные данные
8
8
2
12
Примечание

В первом наборе входных данных би-таблицу можно разбить следующим образом:

  • $$$\begin{bmatrix} 0\\ 1 \end{bmatrix}$$$, $$$\operatorname{MEX}$$$ равен $$$2$$$.
  • $$$\begin{bmatrix} 10\\ 10 \end{bmatrix}$$$, $$$\operatorname{MEX}$$$ равен $$$2$$$.
  • $$$\begin{bmatrix} 1\\ 1 \end{bmatrix}$$$, $$$\operatorname{MEX}$$$ равен $$$0$$$.
  • $$$\begin{bmatrix} 0\\ 1 \end{bmatrix}$$$, $$$\operatorname{MEX}$$$ равен $$$2$$$.
  • $$$\begin{bmatrix} 0\\ 0 \end{bmatrix}$$$, $$$\operatorname{MEX}$$$ равен $$$1$$$.
  • $$$\begin{bmatrix} 0\\ 0 \end{bmatrix}$$$, $$$\operatorname{MEX}$$$ равен $$$1$$$.

Сумма $$$\operatorname{MEX}$$$ равна $$$8$$$.