B. Plus-Minus Splittime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a string s of length n consisting of characters "+" and "-". s represents an array a of length n defined by a_i=1 if s_i= "+" and a_i=-1 if s_i= "-".You will do the following process to calculate your penalty:   Split a into non-empty arrays b_1,b_2,\ldots,b_k such that b_1+b_2+\ldots+b_k=a^\dagger, where + denotes array concatenation.  The penalty of a single array is the absolute value of its sum multiplied by its length. In other words, for some array c of length m, its penalty is calculated as p(c)=|c_1+c_2+\ldots+c_m| \cdot m.  The total penalty that you will receive is p(b_1)+p(b_2)+\ldots+p(b_k). If you perform the above process optimally, find the minimum possible penalty you will receive.^\dagger Some valid ways to split a=[3,1,4,1,5] into (b_1,b_2,\ldots,b_k) are ([3],[1],[4],[1],[5]), ([3,1],[4,1,5]) and ([3,1,4,1,5]) while some invalid ways to split a are ([3,1],[1,5]), ([3],[\,],[1,4],[1,5]) and ([3,4],[5,1,1]).InputEach test contains multiple test cases. The first line contains a single integer t (1 \leq t \leq 1000) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer n (1 \le n \le 5000) — the length of string s.The second line of each test case contains string s (s_i \in \{ \mathtt{+}, \mathtt{-} \}, |s| = n).Note that there are no constraints on the sum of n over all test cases.OutputFor each test case, output a single integer representing the minimum possible penalty you will receive.ExampleInput
51+5-----6+-+-+-10--+++++++-20+---++++-+++++---++-Output
1
5
0
4
4
NoteIn the first test case, we have a=[1]. We can split array a into ([1]). Then, the sum of penalties of the subarrays is p([1]) = 1.In the second test case, we have a=[-1,-1,-1,-1,-1]. We can split array a into ([-1],[-1],[-1],[-1],[-1]). Then, the sum of penalties of the subarrays is p([-1]) + p([-1]) + p([-1]) + p([-1]) + p([-1]) = 1 + 1 + 1 + 1 + 1 = 5.In the third test case, we have a=[1,-1,1,-1,1,-1]. We can split array a into ([1,-1,1,-1],[1,-1]). Then, the sum of penalties of the subarrays is p([1,-1,1,-1]) + p([1,-1]) = 0 + 0 = 0.
51+5-----6+-+-+-10--+++++++-20+---++++-+++++---++-
1 5 0 4 4 
['greedy', '*800']