| Codeforces Round 736 (Div. 2) |
|---|
| Закончено |
Дана шахматная доска размера $$$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$$$.
