在你穿越计算机宇宙的旅程中,你偶然发现了一个非常有趣的世界。这是一条具有 $$$n$$$ 连续单元格的路径,每个单元格可以是空的、包含荆棘或硬币。在一次移动中,您可以沿着路径移动一到两个单元格,前提是目标单元格不包含荆棘(并且属于路径)。如果你带着硬币移动到牢房,你就会捡起它。
这里,绿色箭头对应于合法的移动,红色箭头对应于非法的移动。
你想收集尽可能多的硬币。如果您从路径最左边的单元格开始,请找出您在发现的世界中可以收集的最大硬币数量。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 路径的长度。
每个测试用例的第二行包含一串 $$$n$$$ 字符,即路径的描述。字符“.”表示空单元格,“@”表示有硬币的单元格,“*”表示有刺的单元格。保证第一个单元格为空。
输出
对于每个测试用例,输出一个整数,即您可以收集的最大硬币数量。
示例
输入 #1
3 10 .@@*@.**@@ 5 .@@@@ 15 .@@..@***..@@@*
输出 #1
3 4 3
注意
第一个示例的图片位于问题陈述中。
这是第二个示例的图片:
这是第三个示例的图片: