该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

shuji有一台思题目学习机，在这个学习机上，shuji买过很多的课，但是shuji是一个很懒的人，每次把买的课直接放到库里面而懒得去打开它。有一天shuji在清点库的时候发现有很多课shuji竟然一次都没有打开！！ shuji因为不同课的听取程度而心情有所变化，所以shuji请你帮他找出不同心情浮动中的最小可能为多少。

Description

你将得到一个长度为 $n$ 的字符串 $s$ ，由字符“ +”和“-”组成。 $s$ 表示长度为 $n$ 的数组代表shuji库中的所有课，如果 $s_i=$ “ +”，则由 $a_i=1$ 定义表示听过这节课； 如果 $s_i=$ “-”，则由 $a_i=-1$ 定义表示未听过这节课。

你需要按照以下步骤计算shuji的心情浮动:

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. shuji的最终心情浮动是 $p(b_1)+p(b_2)+\ldots+p(b_k)$ 。

如果你以最佳方式执行上述过程，请找出shuji最小可能出现的心情浮动是多少。

$^\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])$ 的无效方法为 $([3,1],[1,5])$ 、 $([3],[\,],[1,4],[1,5])$ 和 $([3,4],[5,1,1])$ 。

Format

Input

每个测试包含多个测试用例。第一行包含一个整数 $t$ ( $1 \leq t \leq 1000$ )ー测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 5000$ )ー字符串 $s$ 的长度。

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

请注意，对于所有测试用例的总和 $n$ ，不存在约束。

Output

对于每个测试用例，输出一个表示shuji最小可能的心情浮动的单个整数。

Samples

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

1
5
0
4
4

Limitation

1s, 1024KiB for each test case.