Вам задана скобочная последовательность \(s\) длины \(n\), где \(n\) четное (без остатка делится на 2). Строка \(s\) состоит из \(\frac{n}{2}\) открывающих скобок '(' и \(\frac{n}{2}\) закрывающих скобок ')'.
За один ход вы можете выбрать ровно одну скобку и передвинуть ее в начало или в конец строки (т.е. вы можете выбрать некоторый индекс \(i\), удалить \(i\)-й символ из \(s\) и вставить его перед или после всех остальных символов в \(s\)).
Ваша задача — найти минимальное количество ходов, необходимое, чтобы получить правильную скобочную последовательность из \(s\). Можно доказать, что ответ всегда существует при данных ограничениях.
Напомним, что такое правильная скобочная последовательность:
- «()» — правильная скобочная последовательность;
- если \(s\) — правильная скобочная последовательность, то «(» + \(s\) + «)» — правильная скобочная последовательность;
- если \(s\) и \(t\) — правильные скобочные последовательности, то \(s\) + \(t\) — правильная скобочная последовательность.
Например, «()()», «(())()», «(())» и «()» являются правильными скобочными последовательностями, а «)(», «()(» и «)))» — нет.
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ на него — минимальное количество ходов, необходимое, чтобы получить правильную скобочную последовательность из \(s\). Можно доказать, что ответ всегда существует при данных ограничениях.
Примечание
В первом наборе тестовых данных примера достаточно передвинуть первую скобку в конец строки.
В третьем наборе тестовых данных примера достаточно передвинуть последнюю скобку в начало строки.
В четвертом наборе тестовых данных примера мы можем выбрать три последние открывающие скобки, переместить их в начало строки и получить «((()))(())».