B. Plus-Minus Split

时间限制：每个测试用例 1 秒 内存限制：每个测试用例 256 MB

你被给定了一个由字符 + 和 - 组成的字符串 s，它的长度为 n。字符串 s 代表一个数组 a，其长度也是 n，数组 a 的元素由如下规则定义：

• 如果 si = "+"，则 ai = 1；
• 如果 si = "-"，则 ai = -1。

接下来，你将进行如下过程来计算你的惩罚值：

你需要将数组 a 分割成多个非空子数组 b1, b2, ..., bk，使得 b1 + b2 + ... + bk = a，其中 + 表示数组的拼接操作。每个子数组的惩罚值为其元素和的绝对值乘以其长度。也就是说，对于某个子数组 c，其惩罚值计算公式为：

p(c)=∣c1+c2+...+cm∣×mp(c) = |c_1 + c_2 + ... + c_m| \times m

其中 m 是子数组 c 的长度。

你需要计算所有子数组的总惩罚值：

p(b1)+p(b2)+...+p(bk)p(b1) + p(b2) + ... + p(bk)

如果你按照最优的方式进行分割，找到最小可能的总惩罚值。

输入

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

每个测试用例由两行组成：

• 第一行包含一个整数 n（$1 \leq n \leq 5000$），表示字符串 s 的长度；
• 第二行包含一个长度为 n 的字符串 s，其中每个字符 si 取值为 + 或 -。

注意：对于所有测试用例，n 的总和没有额外的限制。

输出

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

示例

输入

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

输出

1
5
0
4
4

说明

• 在第一个测试用例中，数组 a = [1]。我们可以将数组 a 分割成子数组 [1]，然后子数组的惩罚值是 |1| × 1 = 1。
• 在第二个测试用例中，数组 a = [-1, -1, -1, -1, -1]。我们可以将数组 a 分割成五个子数组 [-1], [-1], [-1], [-1], [-1]，然后总惩罚值为 1 + 1 + 1 + 1 + 1 = 5。
• 在第三个测试用例中，数组 a = [1, -1, 1, -1, 1, -1]。我们可以将数组 a 分割成 [1, -1, 1, -1] 和 [1, -1]，总惩罚值为 0 + 0 = 0。