B. Плюс-минус разделение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из символов «+» и «-». По строке $$$s$$$ можно построить массив $$$a$$$ длины $$$n$$$, в котором $$$a_i=1$$$, если $$$s_i=$$$ «+» и $$$a_i=-1$$$, если $$$s_i=$$$ «-».

Чтобы вычислить штраф, нужно выполнить следующие действия:

  1. Разбить массив $$$a$$$ на непустые массивы $$$b_1,b_2,\ldots,b_k$$$ такие, что $$$b_1+b_2+\ldots+b_k=a^\dagger$$$, где $$$+$$$ обозначает конкатенацию массивов.
  2. Штраф одного массива — это модуль его суммы, умноженный на его длину. Другими словами, для некоторого массива $$$c$$$ длины $$$m$$$ его штраф вычисляется как $$$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$$$ по всем наборам входных данных не накладываются дополнительные ограничения.

Выходные данные

Для каждого набора входных данных выведите одно целое число, представляющее собой минимальный возможный штраф, который вы можете получить.

Пример
Входные данные
5
1
+
5
-----
6
+-+-+-
10
--+++++++-
20
+---++++-+++++---++-
Выходные данные
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$$$.