A. 荆棘与硬币
每次测试时间限制：$1$ 秒
每次测试内存限制：$512$ 兆字节

在你穿越计算机宇宙的旅途中，你偶然发现了一个非常有趣的世界。它是由 $n$ 个连续单元格组成的一条路径，每个单元格可以是空的、有荆棘的，或者有硬币的。在一次移动中，你可以沿着路径移动 一格或两格，前提是目标单元格不能有荆棘（并且必须属于这条路径）。如果你移动到一个有硬币的单元格，你会捡起它。

（图中：绿色箭头表示合法移动，红色箭头表示非法移动。）

你想要收集尽可能多的硬币。如果你从路径的最左侧单元格出发，找出你在这个发现的世界中能收集到的最大硬币数量。

输入

第一行输入包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。
接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$）——路径的长度。
每个测试用例的第二行包含一个长度为 $n$ 的字符串，表示路径的描述。

• '.' 表示空单元格
• '@' 表示有硬币的单元格
• '*' 表示有荆棘的单元格

保证第一个单元格是空的。

输出

对于每个测试用例，输出一个整数，表示你可以收集的最大硬币数量。

示例

输入

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

输出

3
4
3

注释

• 第一个示例的图片在题目描述中。
• 第二个示例的图片如下：

• 第三个示例的图片如下：