题目描述

Filip 有一行单元格，一些是障碍物，另一些是空的。他希望把所有空的单元格都灌上水，为此可以进行如下两种操作:

• $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$ ) ，为单元格个数。第二行一个$n$长度字符串 $s$，其中第$i$ 个字符为'.' 表示格子 $i$是空的， '#' 表示格子 $i$ 是障碍物。

输出格式

对每组数据，在一行中输出最小的操作1次数。

样例

5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#

2
2
5
0
2