No submission language available for this problem.

Background

Special for beginners, ^_^

Description

关小山面前有一行格子，有些格子是实心的，有些是空的。他希望所有的空心格子都能够填满水，因此他有下面两种操作：

• 1-将水放到一个格子中。
• 2-将一个格子中的水移动到另一个空的格子里。

不过这些格子有一个特殊的地方，若某个空格子的相邻两边都是满水的，那么它会自己被水填满，并不需要人为操作。

请找出，关小山能够用水填满所有空格子的操作 1 的最少次数。

注意这里只关心操作 1 的次数，操作 2 的次数无所谓。

Format

Input

第一行一个整数 t 表示有 t 组测试。

每组测试第一行一个整数 n 表示有 n 个格子。（1 <= n <= 100）

每组测试第二行有 n 个整数，. 表示空格子，# 表示实心格子。

Output

输出有 t 行，每行一个整数对应一组测试的最少操作 1 的次数。

Samples

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

2
2
5
0
2

Limitation

1s, 1024KiB for each test case.