← 返回题目列表

Codeforces · 1520/E

E. 安排羊

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

您正在玩“排列羊”游戏。这个游戏的目标是让羊排队。游戏中的关卡由长度为 $$$n$$$ 的字符串描述,由字符“.”组成。 (空白)和“*”(羊)。在一次移动中,如果相应的方格存在且为空,您可以将任意羊向左移动一格或向右移动一格。一旦羊排成一排,即任何羊之间不应该有空格,游戏就结束。

例如,如果$$$n=6$$$并且级别由字符串“**.*..”描述,则可能出现以下游戏场景:

- $$$4$$$位置的羊向右移动,关卡状态:“**..*.”;
- $$$2$$$位置的羊向右移动,关卡状态:“*.*.*.”;
- $$$1$$$位置的羊向右移动,关卡状态:“.**.*.”;
- $$$3$$$位置的羊向右移动,关卡状态:“.*.**.”;
- $$$2$$$位置的羊向右移动,关卡状态:“..***.”;
- 羊排好队,游戏结束。

对于给定的关卡,确定完成该关卡所需的最少移动次数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串,由字符“.”组成。 (空格)和“*”(羊)— 关卡的描述。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出完成关卡所需的最小移动次数。

示例

输入 #1

5
6
**.*..
5
*****
3
.*.
3
...
10
*.*...*.**

输出 #1

1
0
0
0
9