#HJ1002. 捡金币

捡金币

【题目描述】

在你穿越多元宇宙的旅程中,你偶然发现了一个非常有趣的世界。这个世界是由一条nn个连续的单元格组成的。每个单元格可以是空的,也可以是硬币,或是荆棘。在一次移动中,你可以沿着路径移动一个或两个单元格,前提是目的地单元格不包含荆棘。如果移动到有硬币的格子,你可以拾起它。

image

你想收集尽可能多的金币。如果你从路径最左边的一格开始,你在这个世界中最多可以收集到多少金币?

【输入格式】

本题的每一次输入中包含了tt个测试用例。 输入的第一行包含一个正整数 t(1𝑡1000)t (1≤𝑡≤1000),表示测试用例的数量。

对每个测试用例:

每个测试用例的第一行包含一个正整数n(1n50)n (1 ≤ n ≤ 50 ),表示路径长度。

每个测试用例的第二行包含一个长度为nn的字符串,该字符串描述了路径上的每个单元格。其中'.'表示该单元格为空,'@'表示单元格中有一个金币, '*'表示单元格为荆棘。数据保证第一个单元格为空。

【输出格式】

对每一个测试用例,输出一个整数,表示你能捡到的金币数量的最大值。

【样例】

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

【提示】

对于第二个测试样例(即第4,5行):

image

对于第三个测试样例(即第6,7行):

image