CF1919B Plus-Minus Split

You 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: 1. 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. 2. 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 $ . 3. 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]) $ .

Each 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.

For each test case, output a single integer representing the minimum possible penalty you will receive.

In 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 $ .