该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小方正在体验一款推箱子游戏。游戏每一关由长度为$n$的字符"_"(一个下划线表示一个空格)和"@"(箱子)组成一个初始状态，让当前所有的箱子集中到一块即可过关。

在一个动作中，如果目标移动的位置存在并且是空的，你可以将任何箱子向左移动一个位置或向右移动一个位置。当前所有箱子已经排好，即任意两个箱子之间都不存在空格，方可进入下一关。

此款游戏共有$t$关，请你帮助小方确定通过每一关卡所需的最小移动次数。

输入格式

第一行，一个正整数$t$，表示关卡的数量。

接下来每$2$行，分别表示每一关的初始情况。

第一行，一个整数$n$，表示当前可用位置的情况。

第二行，一个长度为$n$的字符串，只包含"_"(一个下划线表示一个空格)和"@"(箱子)。

输出格式

输出共$t$行，每一行表示通过每一关卡所需的最小移动次数。

样例输入1

3
6
@@_@__
3
_@_
10
@_@___@_@@

样例输出1

1
0
9

数据范围

对于$30\%$的数据，$1\le t \le 10,1\le \sum n_i \le 10^3$

对于$60\%$的数据，$1\le t \le 10^3,1\le \sum n_i \le 5\times10^5$

对于$100\%$的数据，$1\le t \le 10^4,1\le \sum n_i \le 10^6$

样例解释

第一关的答案：将最右边的箱子向左移动$1$个单位变成@@@___。

第二关的答案：不需要移动，还是_@_。

第三关的答案：左边的第$2$个箱子向右移动$3$个单位变成@____@@_@@、最左边箱子向右移动$4$个单位变成____@@@_@@、右边第$2$个箱子向左移动$1$个单位变成____@@@@_@、最右边箱子向左移动$1$个单位变成____@@@@@_，答案就是$3+4+1+1=9$。