C. Перемещай скобки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

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

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

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

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

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

Пример
Входные данные
4
2
)(
4
()()
8
())()()(
10
)))((((())
Выходные данные
1
0
1
3
Примечание

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

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

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