Задано клетчатое поле, состоящее из $$$2$$$ строк и $$$n$$$ столбцов. Каждая клетка поля либо свободна, либо заблокирована.
Свободная клетка $$$y$$$ достижима из свободной клетки $$$x$$$, если выполняется хотя бы одно из следующих условий:
- $$$x$$$ и $$$y$$$ имеют общую сторону;
- существует свободная клетка $$$z$$$, такая что $$$z$$$ достижима из $$$x$$$, и $$$y$$$ достижима из $$$z$$$.
Связный регион — это множество свободных клеток поля, такое что все клетки в нем достижимы друг из друга, но добавление любой другой свободной клетки в множество нарушает это правило.
Например, рассмотрим следующую ситуацию, где белые клетки свободны, а темно-серые клетки заблокированы:
Здесь $$$3$$$ региона, обозначенные красным, зеленым и синим цветами соответственно:
Заданное поле содержит не более $$$1$$$ связного региона. Ваша задача — посчитать количество свободных клеток, удовлетворяющих следующему условию:
- если клетку заблокировать, то количество связных регионов станет равно $$$3$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество столбцов.
$$$i$$$-я из следующих двух строк содержит описание $$$i$$$-й строки поля — строку $$$s_i$$$, состоящую из $$$n$$$ символов. Каждый символ является либо . (обозначающим свободную клетку), либо x (обозначающим заблокированную клетку).
Дополнительные ограничения на входные данные:
- заданное поле содержит не более $$$1$$$ связную область;
- сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество клеток, при блокировке которых количество связных регионов станет равно $$$3$$$.
48.......x.x.xx...2....3xxxxxx9..x.x.x.xx.......x
1 0 0 2
В первом наборе входных данных, если заблокировать клетку $$$(1, 3)$$$, количество регионов станет равно $$$3$$$ (смотрите картинку в условии задачи).
