题目描述

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

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

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

输入格式

第一行：一个整数 $t$，表示 $t$ 个关卡。

接下来是 $2t$ 行表示每一关初始情况。

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

一个长度为 $n$ 的字符串，只包含“_”(空格)和(空格)和“@”(箱子)

输出格式

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

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

1
0
9

说明

@@@___ (最右边箱子向左移动 $1$ 个单位)

_@_(移动 $0$ 次)

$3 + 4 + 1 + 1 = 9$。左边第 $2$ 个箱子向右移动 $3$ 个单位、最左边箱子向右移动 $4$ 个单位、 右边第 $2$ 个箱子向左移动 $1$ 个单位、最右边箱子向左移动 $1$ 个单位

数据范围

对于 $30\%$ 的数据，$1≤t≤10,1≤∑n_i≤10^3$。

对于 $60\%$ 的数据，$1≤t≤10^3,1≤∑n_i≤5∗10^5$。

对于 $100\%$ 的数据，$1≤t≤10^4,1≤∑n_i≤10^5$。