C. Джерримендеринг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Все мы понемногу воруем. Но у меня только одна рука, а у моих противников — две.
Álvaro Obregón, бывший президент Мексики

Альваро и Хосе — единственные кандидаты, претендующие на пост президента Тепито — прямоугольной сетки из $$$2$$$ строк и $$$n$$$ столбцов, где каждая клетка представляет собой дом. Гарантируется, что $$$n$$$ кратно $$$3$$$.

Согласно системе голосования Тепито, сетка будет разбита на округа, состоящие из любых $$$3$$$ домов, которые связаны между собой$$$^{\text{∗}}$$$. Каждый дом будет принадлежать ровно одному округу.

Каждый округ будет голосовать один раз. Округ будет голосовать за Альваро или Хосе соответственно, если их выберут не менее $$$2$$$ домов в этом округе. Таким образом, всего будет подано $$$\frac{2n}{3}$$$ голосов.

Поскольку Альваро является действующим президентом, он точно знает, какого кандидата выберет каждый дом. Определите максимальное количество голосов, которое Альваро может получить, если он оптимально распределит дома по округам.

$$$^{\text{∗}}$$$Набор клеток является связанным, если между любыми $$$2$$$ клетками существует путь, который требует только перемещения вверх, вниз, влево и вправо по клеткам набора.

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

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

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

В следующих двух строках содержится по строке длины $$$n$$$. В $$$i$$$-й строке содержится строка $$$s_i$$$, состоящая из символов $$$\texttt{A}$$$ и $$$\texttt{J}$$$. Если $$$s_{i,j}=\texttt{A}$$$, то дом на пересечении $$$i$$$-й строки и $$$j$$$-го столбца выберет Альваро. В противном случае, если $$$s_{i,j}=\texttt{J}$$$, дом проголосует за Хосе.

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

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

Для каждого набора входных данных выведите одно целое число — максимальное количество округов, которое может выиграть Альваро, оптимально разделив дома на округа.

Пример
Входные данные
4
3
AAA
AJJ
6
JAJAJJ
JJAJAJ
6
AJJJAJ
AJJAAA
9
AJJJJAJAJ
JAAJJJJJA
Выходные данные
2
2
3
2
Примечание

На изображении ниже показано оптимальное разбиение на округа, которое Альваро может использовать для каждого набора входных данных в примере.