B. 正负号拆分
时间限制：每个测试点 $1$ 秒
内存限制：$256$ 兆字节

给定一个长度为 $n$ 的字符串 $s$，由字符 "+" 和 "-" 组成。
$s$ 表示一个长度为 $n$ 的数组 $a$，定义如下：

• 若 $s_i = \texttt{"+"}$，则 $a_i = 1$；
• 若 $s_i = \texttt{"-"}$，则 $a_i = -1$。

你将通过以下过程计算你的罚分：

1. 将数组 $a$ 拆分成若干个非空数组 $b_1, b_2, \dots, b_k$，满足 $b_1 + b_2 + \dots + b_k = a$（这里的 $+$ 表示数组的连接）。
2. 一个数组 $c$（长度为 $m$）的罚分定义为：$$p(c) = |c_1 + c_2 + \dots + c_m| \cdot m$$
3. 总罚分为：$$p(b_1) + p(b_2) + \dots + p(b_k)$$

如果你能最优地进行拆分，请输出你能获得的最小总罚分。

输入格式

每个测试包含多个测试用例。
第一行一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。
每个测试用例两行：

• 第一行一个整数 $n$（$1 \le n \le 5000$）——字符串 $s$ 的长度。
• 第二行一个字符串 $s$（$s_i \in \{ \texttt{+}, \texttt{-} \}$，$|s| = n$）。

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

输出格式

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

示例

输入：

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

输出：

1
5
0
4
4

示例解释

第一个测试用例：
$a = [1]$。
唯一拆分：$([1])$。
罚分：$p([1]) = 1$。

第二个测试用例：
$a = [-1, -1, -1, -1, -1]$。
拆分：$([-1],[-1],[-1],[-1],[-1])$。
罚分：$1 + 1 + 1 + 1 + 1 = 5$。

第三个测试用例：
$a = [1, -1, 1, -1, 1, -1]$。
拆分：$([1, -1, 1, -1], [1, -1])$。
罚分：$0 + 0 = 0$。