Cover in Water
Contest: Codeforces Round 911 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, implementation, strings

Filip has a row of cells, some of which are blocked, and some are empty. He wants all empty cells to have water in them. He has two actions at his disposal:

- $$$1$$$ — place water in an empty cell.
- $$$2$$$ — remove water from a cell and place it in any other empty cell.

If at some moment cell $$$i$$$ ($$$2 \le i \le n-1$$$) is empty and both cells $$$i-1$$$ and $$$i+1$$$ contains water, then it becomes filled with water.

Find the minimum number of times he needs to perform action $$$1$$$ in order to fill all empty cells with water.

Note that you don't need to minimize the use of action $$$2$$$. Note that blocked cells neither contain water nor can Filip place water in them.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of cells.

The next line contains a string $$$s$$$ of length $$$n$$$. The $$$i$$$-th character of $$$s$$$ is '.' if the cell $$$i$$$ is empty and '#' if cell $$$i$$$ is blocked.

Output format:
For each test case, output a single number — the minimal amount of actions $$$1$$$ needed to fill all empty cells with water.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Test Case 1

In the first test case, Filip can put water in cells $$$1$$$ and $$$3$$$. As cell $$$2$$$ is between $$$2$$$ cells with water, it gets filled with water too.

Test Case 2

In the second case, he can put water sources in cells $$$3$$$ and $$$5$$$. That results in cell $$$4$$$ getting filled with water. Then he will remove water from cell $$$5$$$ and place it into cell $$$6$$$. As cell $$$5$$$'s neighbors, cell $$$4$$$ and cell $$$6$$$, have water in them, cell $$$5$$$ also gets filled with water. You can see the illustration of this case below.

Operations in the second test case. White cells are empty, grey ones are blocked, and blue ones are water.

Test Case 3

In the third case, he can put water in all the empty cells. That requires $$$5$$$ actions of type $$$1$$$.

Test Case 4

In the fourth case, there are no empty cells. Therefore, he does not have to put any water in them.

Test Case 5

In the fifth test case, there exists a sequence of actions that requires only $$$2$$$ type $$$1$$$ actions.

Example input:
5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#

Example output:
2
2
5
0
2

Editorial:
If there is an index $$$i$$$ such that the cells $$$i$$$, $$$i+1$$$ and $$$i+2$$$ are all empty, we can perform the action $$$1$$$ on the cells with the indexes $$$i$$$ and $$$i+2$$$. By doing so, the cell $$$i+1$$$ will also become filled with water. Now we can by performing the action $$$2$$$, remove water from the cell $$$i+1$$$ and place it in a cell which is empty. We can repeat the action $$$2$$$ this way until all empty cells become filled with water. That is because the cell $$$i+1$$$ will remain filled with water because it's between the cells $$$i$$$ and $$$i+2$$$ which are filled with water. We conclude that the answer will be 2.
If there is no such index $$$i$$$, we can't create more water using the action $$$2$$$. We need to fill all empty cells with water using action $$$1$$$. The answer in this case is number of empty cells.