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$$$。 $$$s$$$ 的第 $$$i$$$ 个字符是“.”如果单元格 $$$i$$$ 为空,则为“#”;如果单元格 $$$i$$$ 被阻止,则为“#”。
输出
对于每个测试用例,输出一个数字 - 将所有空单元格注满水所需的最小操作量 $$$1$$$。
示例
输入 #1
5 3 ... 7 ##....# 7 ..#.#.. 4 #### 10 #...#..#.#
输出 #1
2 2 5 0 2
注意
测试用例1
在第一个测试用例中,Filip 可以将水放入单元格 $$$1$$$ 和 $$$3$$$ 中。由于单元格 $$$2$$$ 位于 $$$2$$$ 单元格之间且有水,因此它也会充满水。
测试用例2
在第二种情况下,他可以将水源放入单元格$$$3$$$和$$$5$$$中。这会导致单元格 $$$4$$$ 充满水。然后他将从 $$$5$$$ 单元中除去水并将其放入 $$$6$$$ 单元中。由于单元格 $$$5$$$ 的邻居单元格 $$$4$$$ 和单元格 $$$6$$$ 中有水,因此单元格 $$$5$$$ 也充满了水。您可以在下面看到此案例的插图。
第二个测试用例中的操作。白色的细胞是空的,灰色的细胞被堵塞,蓝色的细胞是水。
测试用例3
在第三种情况下,他可以将水放入所有空单元格中。这需要 $$$5$$$ 类型的操作 $$$1$$$。
测试用例4
在第四种情况下,没有空单元格。因此,他不必在其中放任何水。
测试用例5
在第五个测试用例中,存在仅需要 $$$2$$$ 类型 $$$1$$$ 操作的操作序列。