题目描述

给定一个长度为 $n$ 的字符串 $s$，由字符 “+” 和 “-” 组成。$s$ 表示一个长度为 $n$ 的数组 $a$，其中当 $s_i$ 为 “+” 时 $a_i=1$，当 $s_i$ 为 “-” 时 $a_i=-1$。

你需要按照如下过程计算你的惩罚值：

1. 将数组 $a$ 拆分为若干个非空数组 $b_1,b_2,\ldots,b_k$，使得 $b_1+b_2+\ldots+b_k=a^\dagger$，其中 $+$ 表示数组拼接。
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])$。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是每组测试用例的描述。

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

第二行包含字符串 $s$（$s_i \in \{ +, - \}$，$|s| = n$）。

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

输出格式

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

说明/提示

在第一个测试用例中，$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$。

由 ChatGPT 4.1 翻译

样例

5
1
+
5
-----
6
+-+-+-
10
--+++++++-
20
+---++++-+++++---++-

1
5
0
4
4