311086: CF1932A. Thorns and Coins

A. Thorns and Coinstime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

During your journey through computer universes, you stumbled upon a very interesting world. It is a path with $n$ consecutive cells, each of which can either be empty, contain thorns, or a coin. In one move, you can move one or two cells along the path, provided that the destination cell does not contain thorns (and belongs to the path). If you move to the cell with a coin, you pick it up.

Here, green arrows correspond to legal moves, and the red arrow corresponds to an illegal move.

You want to collect as many coins as possible. Find the maximum number of coins you can collect in the discovered world if you start in the leftmost cell of the path.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 50$) — the length of the path.

The second line of each test case contains a string of $n$ characters, the description of the path. The character '.' denotes an empty cell, '@' denotes a cell with a coin, and '*' denotes a cell with thorns. It is guaranteed that the first cell is empty.

Output

For each test case, output a single integer, the maximum number of coins you can collect.

ExampleInput

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

Output

3
4
3

Note

The picture for the first example is in the problem statement.

Here is the picture for the second example:

And here is the picture for the third example:

题目大意：
你在一个由连续的格子组成的路径上，每个格子可能是空的、有刺或有硬币。你可以一次移动一个或两个格子，只要目标格子没有刺（且在路径上）。如果你移动到一个有硬币的格子，你会捡起它。目标是收集尽可能多的硬币。你需要找出从路径最左边的格子开始，你能收集的最大硬币数量。

输入数据格式：
第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤50），表示路径的长度。
每个测试用例的第二行包含一个由n个字符组成的字符串，描述路径。字符'.'表示空格子，'@'表示有硬币的格子，'*'表示有刺的格子。保证第一个格子是空的。

输出数据格式：
对于每个测试用例，输出一个整数，表示你能收集的最大硬币数量。

示例：
输入：
3
10
.@@*@.**@@
5
.@@@@
15
.@@..@***..@@@*

输出：
3
4
3

注意：
题目描述中给出了第一个示例的图片。第二个和第三个示例的图片在题目描述之外。题目大意： 你在一个由连续的格子组成的路径上，每个格子可能是空的、有刺或有硬币。你可以一次移动一个或两个格子，只要目标格子没有刺（且在路径上）。如果你移动到一个有硬币的格子，你会捡起它。目标是收集尽可能多的硬币。你需要找出从路径最左边的格子开始，你能收集的最大硬币数量。 输入数据格式： 第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤50），表示路径的长度。 每个测试用例的第二行包含一个由n个字符组成的字符串，描述路径。字符'.'表示空格子，'@'表示有硬币的格子，'*'表示有刺的格子。保证第一个格子是空的。 输出数据格式： 对于每个测试用例，输出一个整数，表示你能收集的最大硬币数量。 示例： 输入： 3 10 .@@*@.**@@ 5 .@@@@ 15 .@@..@***..@@@* 输出： 3 4 3 注意： 题目描述中给出了第一个示例的图片。第二个和第三个示例的图片在题目描述之外。