E. Двигающиеся фигуры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана доска размера $$$2 \times n$$$ ($$$2$$$ строки, $$$n$$$ столбцов). В некоторых клетках доски находятся фигуры. Фигура представлена символом '*', а пустое место представлено символом '.'. Гарантируется, что на доске находится хотя бы одна фигура.

За один ход вы можете выбрать любую фигуру и сдвинуть ее в любую соседнюю (по стороне) клетку доски (если эта клетка находится на доске). Это значит, что если фигура находится в первом ряду, вы можете сдвинуть ее влево, вправо или вниз (но она не должна покидать пределы доски). То же самое с фигурой во второй строке — вы можете сдвинуть ее влево, вправо или вверх.

Если фигура попадает в клетку с другой фигурой, фигура в клетке назначения исчезает (то есть наша фигура ест ее).

Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы оставить ровно одну фигуру на доске.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

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

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину доски. Вторая строка набора тестовых данных содержит строку $$$s_1$$$, состоящую из $$$n$$$ символов '*' (фигура) и/или '.' (пустая клетка). Третья строка набора тестовых данных содержит строку $$$s_2$$$, состоящую из $$$n$$$ символов '*' (фигура) и/или '.' (пустая клетка).

Дополнительные ограничения на входные данные:

  • в каждом наборе тестовых данных есть хотя бы одна фигура на доске;
  • сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).
Выходные данные

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

Пример
Входные данные
5
1
*
.
2
.*
**
3
*.*
.*.
4
**.*
**..
5
**...
...**
Выходные данные
0
2
3
5
5