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

Дана таблица размера $$$2 \times n$$$, каждая клетка которой либо пуста, либо содержит одну лягушку. Гарантируется, что в каждом столбце исходной таблицы находится хотя бы одна лягушка. Вы можете выбрать $$$k$$$ лягушек и убрать их из таблицы. После этого все оставшиеся лягушки прыгнут.

Каждая лягушка может прыгнуть на $$$1$$$ клетку вверх, вниз, влево или вправо, но не может выпрыгнуть за пределы таблицы. Все лягушки должны выбрать допустимое направление и одновременно совершить ровно один прыжок. После прыжков количество лягушек в каждой строке и каждом столбце таблицы должно остаться неизменным.

Обратите внимание:

  • Даже если направления прыжков двух лягушек конфликтуют, они всё равно могут прыгнуть в соответствующие целевые клетки.
  • Нескольким лягушкам разрешается прыгнуть в одну клетку, поскольку клетка может содержать произвольное количество лягушек.

Найдите минимальное $$$k$$$, при котором существует допустимая схема прыжков.

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

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

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

Каждая из следующих двух строк содержит строку длины $$$n$$$: символом $$$\texttt{f}$$$ обозначается клетка с лягушкой, а символом $$$\texttt{o}$$$ — пустая клетка.

Гарантируется, что в каждом столбце исходной таблицы находится хотя бы одна лягушка.

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

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

Для каждого набора входных данных выведите одну строку, содержащую минимальное $$$k$$$, при котором существует допустимая схема прыжков.

Пример
Входные данные
4
2
ff
oo
2
fo
of
3
fof
ofo
1
f
o
Выходные данные
0
0
1
1
Примечание

В первом наборе входных данных две лягушки могут прыгнуть в клетки друг друга.

Во втором наборе входных данных левая лягушка может прыгнуть вниз, а правая — вверх. После прыжков общее количество лягушек в каждой строке и каждом столбце остаётся равным $$$1$$$.

of
fo

В третьем наборе входных данных все три лягушки могут прыгнуть в одну клетку $$$(1,2)$$$, однако это не является допустимым ответом, поскольку количество лягушек в первом столбце изменяется с $$$1$$$ до $$$0$$$.

of f fo
ooo