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

У Филиппа есть ряд клеток, некоторые из которых заблокированы, а остальные — пусты. Он хочет, чтобы во всех пустых клетках оказалась вода. Для этого он может применять 2 типа операций:

  • $$$1$$$ — поместить воду в пустую клетку.
  • $$$2$$$ — переместить воду из клетки с водой в любую другую пустую клетку. Обратите внимание, что при перемещении воды из одной клетки в другую Филипп удаляет воду из начальной клетки.

Если клетка $$$i$$$ ($$$2 \le i \le n-1$$$) пустая, а клетки $$$i-1$$$ и $$$i+1$$$ содержат воду, то она заполняется водой.

Найдите минимальное количество раз, которое ему нужно выполнить операцию $$$1$$$ типа, чтобы заполнить все пустые клетки водой.

Заметим, что минимизировать использование операций $$$2$$$ типа не нужно. Также заметим, что заблокированные клетки не содержат воду, и Филипп не может поместить в них воду.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество клеток.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$. $$$i$$$-й символ $$$s$$$ равен '.', если клетка $$$i$$$ пуста, и '#', если клетка $$$i$$$ заблокирована.

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

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

Пример
Входные данные
5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#
Выходные данные
2
2
5
0
2
Примечание

Набор входных данных 1

В первом наборе входных данных Филипп может поместить воду в клетки $$$1$$$ и $$$3$$$. Поскольку клетка $$$2$$$ находится между $$$2$$$ клетками с водой, она тоже заполняется водой.

Набор входных данных 2

Во втором наборе он может поместить источники воды в клетки $$$3$$$ и $$$5$$$. В результате клетка $$$4$$$ заполнится водой. Затем он удалит воду из клетки $$$5$$$ и поместит ее в клетку $$$6$$$. Поскольку соседи клетки $$$5$$$ — клетки $$$4$$$ и $$$6$$$ — имеют воду, клетка $$$5$$$ также заполняется водой. Иллюстрация этого процесса приведена ниже.

Операции во втором наборе входных данных. Белые клетки — пустые, серые — заблокированные, синие — вода.

Набор входных данных 3

В третьем наборе входных данных он может поместить воду во все пустые клетки. Для этого требуется $$$5$$$ операций $$$1$$$ типа.

Набор входных данных 4

В четвертом наборе пустых клеток нет. Следовательно, ни одной операции применять не нужно.

Набор входных данных 5

В пятом наборе входных данных существует последовательность операций, которая требует только $$$2$$$ операции типа $$$1$$$.