您正在玩“排列羊”游戏。这个游戏的目标是让羊排队。游戏中的关卡由长度为 $$$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