← 返回题目列表

Codeforces · 1932/A

A. 荆棘和硬币

中文机器翻译题面 查看原题

在你穿越计算机宇宙的旅程中,你偶然发现了一个非常有趣的世界。这是一条具有 $$$n$$$ 连续单元格的路径,每个单元格可以是空的、包含荆棘或硬币。在一次移动中,您可以沿着路径移动一到两个单元格,前提是目标单元格不包含荆棘(并且属于路径)。如果你带着硬币移动到牢房,你就会捡起它。

这里,绿色箭头对应于合法的移动,红色箭头对应于非法的移动。

你想收集尽可能多的硬币。如果您从路径最左边的单元格开始,请找出您在发现的世界中可以收集的最大硬币数量。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 路径的长度。

每个测试用例的第二行包含一串 $$$n$$$ 字符,即路径的描述。字符“.”表示空单元格,“@”表示有硬币的单元格,“*”表示有刺的单元格。保证第一个单元格为空。

输出

对于每个测试用例,输出一个整数,即您可以收集的最大硬币数量。

示例

输入 #1

3
10
.@@*@.**@@
5
.@@@@
15
.@@..@***..@@@*

输出 #1

3
4
3

注意

第一个示例的图片位于问题陈述中。

这是第二个示例的图片:

这是第三个示例的图片: