给定一个字符串 $$$s$$$,长度为 $$$n$$$,由字符“+”和“-”组成。 $$$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])$$$ 而分割 $$$a$$$ 的一些无效方法是 $$$([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 \{ \mathtt{+}, \mathtt{-} \}$$$, $$$|s| = n$$$)。
请注意,所有测试用例的 $$$n$$$ 总和没有限制。
输出
对于每个测试用例,输出一个整数,表示您将收到的最小可能惩罚。
示例
输入 #1
5 1 + 5 ----- 6 +-+-+- 10 --+++++++- 20 +---++++-+++++---++-
输出 #1
1 5 0 4 4
注意
在第一个测试用例中,我们有 $$$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$$$。