B. Грегор и игра в пешки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана шахматная доска размера $$$n$$$ на $$$n$$$. Клетка на пересечении $$$i$$$-й сверху ряду и $$$j$$$-го слева столбца обозначается как $$$(i,j)$$$.

На данный момент у Грегора есть несколько пешек в $$$n$$$-м ряду. Также в $$$1$$$-м ряду стоят вражеские пешки. За один шаг Грегор перемещает одну из своих пешек. Пешка может ходить на одну клетку вверх (из $$$(i,j)$$$ в $$$(i-1,j)$$$), если клетка назначения не занята другой пешкой. В дополнение, пешка может переместиться на одну клетку вверх по диагонали (из $$$(i,j)$$$ в $$$(i-1,j-1)$$$ или в $$$(i-1,j+1)$$$), если и только если в этой клетке стоит вражеская пешка. Вражеская пешка в таком случае убирается с доски.

Грегор хочет узнать, какое максимальное количество его пешек может достичь $$$1$$$-го ряда.

Заметьте, что в этой игре ходит только Грегор, вражеские пешки никогда не перемещаются. Также, когда пешка Грегора достигает $$$1$$$-го ряда, она останавливается и больше не может перемещаться.

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

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1\le t\le 2\cdot 10^4$$$) — количество наборов входных данных. Далее следует описание этих $$$t$$$ наборов.

Каждый набор входных данных состоит из трех строк. Первая строка содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot{10}^{5}$$$) — размер доски.

Вторая строка содержит бинарную строку длины $$$n$$$, в которой $$$1$$$ на $$$i$$$-й позиции соответствует вражеской пешке в $$$i$$$-й слева клетке в первом ряду, а $$$0$$$ соответствует пустой клетке.

Третья строка содержит бинарную строку длины $$$n$$$, в которой $$$1$$$ на $$$i$$$-й позиции соответствует пешке Грегора в $$$i$$$-й слева клетке в последнем ряду, а $$$0$$$ соответствует пустой клетке.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных меньше $$$2\cdot{10}^{5}$$$.

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

Для каждого набора входных данных выведите одно целое число: максимальное количество пешек Грегора, которые могут достичь $$$1$$$-го ряда.

Пример
Входные данные
4
3
000
111
4
1111
1111
3
010
010
5
11001
00000
Выходные данные
3
4
0
0
Примечание

В первом примере Грегор может просто переместить вперед все его $$$3$$$ пешки. Таким образом, ответ равен $$$3$$$.

Во втором примере Грегор может гарантировать, что все его $$$4$$$ пешки достигнут вражеского ряда, следуя раскрашенным путям как показано ниже. Помните — только Грегор делает ходы в этой «игре»!

В третьем примере единственная пешка Грегора застряла перед вражеской пешкой и не может достигнуть желаемого ряда.

В четвертом примере у Грегора нет пешек, поэтому ответ равен $$$0$$$.