CF1900A.Cover in Water

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.

菲利普有一排单元格，其中一些被阻塞，另一些为空。他希望所有空单元格中都充满水。他可以执行以下两种操作：

• $1$ — 在一个空单元格中放置水；
• $2$ — 将某个单元格中的水移除，并将其放置到任意其他空单元格中。

若在某一时刻，单元格 $i$（其中 $2 \le i \le n-1$）为空，且其左右相邻单元格 $i-1$ 和 $i+1$ 均含有水，则该单元格 $i$ 会自动被水填满。

求为使所有空单元格均被水填满，所需执行操作 $1$ 的最小次数。

注意：你无需最小化操作 $2$ 的使用次数。另外，被阻塞的单元格既不能存水，菲利普也不能向其中放置水。

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.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）—— 表示单元格的数量。

下一行包含一个长度为 $n$ 的字符串 $s$。字符串 $s$ 的第 $i$ 个字符为 '.' 表示第 $i$ 个单元格为空，为 '#' 表示第 $i$ 个单元格被阻塞。

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

对于每个测试用例，输出一个整数——即填满所有空单元格所需的最少操作次数 $1$。

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.

测试用例 1

在第一个测试用例中，Filip 可以在第 $1$ 和第 $3$ 个格子中注水。由于第 $2$ 个格子位于两个有水的格子之间，它也会被水填满。

测试用例 2

在第二个测试用例中，他可以在第 $3$ 和第 $5$ 个格子中放置水源。这将导致第 $4$ 个格子被水填满。随后，他将第 $5$ 个格子中的水移除，并将其注入第 $6$ 个格子。由于第 $5$ 个格子的相邻格子（即第 $4$ 和第 $6$ 个格子）均有水，因此第 $5$ 个格子也会被水填满。该情况的示意图如下所示。

第二个测试用例中的操作。白色格子为空，灰色格子为障碍物，蓝色格子为水。

测试用例 3

在第三个测试用例中，他可以向所有空格子中注水。这需要执行 $5$ 次类型 $1$ 的操作。

测试用例 4

在第四个测试用例中，不存在空格子。因此，他无需向任何格子中注水。

测试用例 5

在第五个测试用例中，存在一种仅需 $2$ 次类型 $1$ 操作的操作序列。