Filip 有一排格子，其中一些被阻塞，另一些为空。他希望所有空格子最终都被水填满。他有两种操作：

1. 在一个空格子中放置水。
2. 从某个格子移走水，并把这份水放到任意另一个空格子中。

此外还有一条自动填充规则： 如果在某一时刻，格子 $i$（$2 \le i \le n-1$）是空的，并且格子 $i-1$ 与 $i+1$ 都含有水，那么格子 $i$ 会自动被水填满。

请你求出，为了让所有空格子都被水填满，最少需要执行多少次操作 1。

注意：

• 不需要最小化操作 2 的使用次数。
• 被阻塞的格子既不会含水，也不能放水。

输入格式

第一行是一个整数 $t$（$1 \le t \le 100$），表示测试用例数量。

每个测试用例包含：

• 第一行一个整数 $n$（$1 \le n \le 100$），表示格子数量；

• 第二行一个长度为 $n$ 的字符串 $s$：

  • 若 $s_i='.'$ 表示第 $i$ 个格子为空；
  • 若 s_i='#' 表示第 $i$ 个格子被阻塞。

输出格式

对每个测试用例输出一行一个整数，表示最少需要执行的操作 1 的次数。

样例

输入：

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

输出：

2
2
5
0
2