@Urugvay

Нужна срочная помощь в решении.


Вам задана скобочная последовательность s длины n, где n четное (без остатка делится на 2). Строка s состоит из n2 открывающих скобок '(' и n2 закрывающих скобок ')'.

За один ход вы можете выбрать ровно одну скобку и передвинуть ее в начало или в конец строки (т.е. вы можете выбрать некоторый индекс i, удалить i-й символ из s и вставить его перед или после всех остальных символов в s).

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

Напомним, что такое правильная скобочная последовательность:

«()» — правильная скобочная последовательность;
если s — правильная скобочная последовательность, то «(» + s + «)» — правильная скобочная последовательность;
если s и t — правильные скобочные последовательности, то s + t — правильная скобочная последовательность.
Например, «()()», «(())()», «(())» и «()» являются правильными скобочными последовательностями, а «)(», «()(» и «)))» — нет.

Вам нужно ответить на t независимых наборов тестовых данных.

Входные данные
Первая строка теста содержит одно целое число t (1≤t≤2000) — количество наборов тестовых данных. Затем следуют t наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число n (2≤n≤50) — длину s. Гарантируется, что n четное. Вторая строка набора тестовых данных содержит строку s, состоящую из n2 открывающих и n2 закрывающих скобок.

Выходные данные
Для каждого набора тестовых данных выведите ответ на него — минимальное количество ходов, необходимое, чтобы получить правильную скобочную последовательность из s. Можно доказать, что ответ всегда существует при данных ограничениях.

Пример
входные данные
4
2
)(
4
()()
8
())()()(
10
)))((((())

выходные данные
1
0
1
3

Примечание
В первом наборе тестовых данных примера достаточно передвинуть первую скобку в конец строки.

В третьем наборе тестовых данных примера достаточно передвинуть последнюю скобку в начало строки.

В четвертом наборе тестовых данных примера мы можем выбрать три последние открывающие скобки, переместить их в начало строки и получить «((()))(())».

0