CF1919B.Plus-Minus Split

You are given a string $s$ of length $n$ consisting of characters "+" and "-". $s$ represents an array $a$ of length $n$ defined by $a_i=1$ if $s_i=$ "+" and $a_i=-1$ if $s_i=$ "-".

You will do the following process to calculate your penalty:

1. Split $a$ into non-empty arrays $b_1,b_2,\ldots,b_k$ such that $b_1+b_2+\ldots+b_k=a^\dagger$, where $+$ denotes array concatenation.
2. The penalty of a single array is the absolute value of its sum multiplied by its length. In other words, for some array $c$ of length $m$, its penalty is calculated as $p(c)=|c_1+c_2+\ldots+c_m| \cdot m$.
3. The total penalty that you will receive is $p(b_1)+p(b_2)+\ldots+p(b_k)$.

If you perform the above process optimally, find the minimum possible penalty you will receive.

$^\dagger$ Some valid ways to split $a=[3,1,4,1,5]$ into $(b_1,b_2,\ldots,b_k)$ are $([3],[1],[4],[1],[5])$, $([3,1],[4,1,5])$ and $([3,1,4,1,5])$ while some invalid ways to split $a$ are $([3,1],[1,5])$, $([3],[\,],[1,4],[1,5])$ and $([3,4],[5,1,1])$.

给你一个长度为 $n$ 的字符串 $s$，它仅由字符 "+" 和 "-" 组成。该字符串表示一个长度为 $n$ 的数组 $a$，其定义为：若 $s_i =$ "+"，则 $a_i = 1$；若 $s_i =$ "-"，则 $a_i = -1$。

你将执行如下过程来计算你的罚分（penalty）：

1. 将数组 $a$ 划分为若干个非空子数组 $b_1, b_2, \ldots, b_k$，使得 $b_1 + b_2 + \ldots + b_k = a^\dagger$，其中 $+$ 表示数组的拼接（concatenation）。
2. 单个子数组的罚分为其元素和的绝对值乘以其长度。换言之，对某个长度为 $m$ 的数组 $c$，其罚分定义为 $p(c) = |c_1 + c_2 + \ldots + c_m| \cdot m$。
3. 你最终获得的总罚分为 $p(b_1) + p(b_2) + \ldots + p(b_k)$。

若你以最优方式执行上述过程，求你能获得的最小可能罚分。

$^\dagger$ 对于 $a = [3, 1, 4, 1, 5]$，一些合法的划分方式 $(b_1, b_2, \ldots, b_k)$ 包括：$([3], [1], [4], [1], [5])$、$([3,1], [4,1,5])$ 和 $([3,1,4,1,5])$；而一些非法的划分方式包括：$([3,1], [1,5])$、$([3], [\,], [1,4], [1,5])$ 以及 $([3,4], [5,1,1])$。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5000$) — the length of string $s$.

The second line of each test case contains string $s$ ($s_i \in { \mathtt{+}, \mathtt{-} }$, $|s| = n$).

Note that there are no constraints on the sum of $n$ over all test cases.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含字符串 $s$（其中 $s_i \in { \mathtt{+}, \mathtt{-} }$，且 $|s| = n$）。

注意：所有测试用例的 $n$ 之和没有额外限制。

For each test case, output a single integer representing the minimum possible penalty you will receive.

对于每个测试用例，输出一个整数，表示你将获得的最小可能罚分。

In the first test case, we have $a=[1]$. We can split array $a$ into $([1])$. Then, the sum of penalties of the subarrays is $p([1]) = 1$.

In the second test case, we have $a=[-1,-1,-1,-1,-1]$. We can split array $a$ into $([-1],[-1],[-1],[-1],[-1])$. Then, the sum of penalties of the subarrays is $p([-1]) + p([-1]) + p([-1]) + p([-1]) + p([-1]) = 1 + 1 + 1 + 1 + 1 = 5$.

In the third test case, we have $a=[1,-1,1,-1,1,-1]$. We can split array $a$ into $([1,-1,1,-1],[1,-1])$. Then, the sum of penalties of the subarrays is $p([1,-1,1,-1]) + p([1,-1]) = 0 + 0 = 0$.

在第一个测试用例中，我们有 $a=[1]$。我们可以将数组 $a$ 分割为 $([1])$。此时，各子数组的惩罚值之和为 $p([1]) = 1$。

在第二个测试用例中，我们有 $a=[-1,-1,-1,-1,-1]$。我们可以将数组 $a$ 分割为 $([-1],[-1],[-1],[-1],[-1])$。此时，各子数组的惩罚值之和为 $p([-1]) + p([-1]) + p([-1]) + p([-1]) + p([-1]) = 1 + 1 + 1 + 1 + 1 = 5$。

在第三个测试用例中，我们有 $a=[1,-1,1,-1,1,-1]$。我们可以将数组 $a$ 分割为 $([1,-1,1,-1],[1,-1])$。此时，各子数组的惩罚值之和为 $p([1,-1,1,-1]) + p([1,-1]) = 0 + 0 = 0$。