C. Четные позиции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа была правильная скобочная последовательность $$$s$$$ длины $$$n$$$ ($$$n$$$ — четное). Он даже придумал свой способ вычисления её стоимости.

Он знает, что в правильной скобочной последовательности (ПСП) каждой открывающей скобке соответствует парная ей закрывающая скобка. Поэтому он решил вычислить стоимость ПСП как сумму расстояний между парами соответствующих скобок.

Например, рассмотрим ПСП (())(). Она состоит из трех пар скобок:

  • (__)__: расстояние между скобками на позициях $$$1$$$ и $$$4$$$ равно $$$4 - 1 = 3$$$;
  • _()___: расстояние равно $$$3 - 2 = 1$$$;
  • ____(): расстояние равно $$$6 - 5 = 1$$$.
Таким образом, стоимость (())() равна $$$3 + 1 + 1 = 5$$$.

К сожалению, из-за повреждения данных Монокарп потерял все символы на нечетных позициях $$$s_1, s_3, \dots, s_{n-1}$$$. Остались только символы на четных позициях ($$$s_2, s_4, \dots, s_{n}$$$). Например, (())() превратилась в _(_)_).

Монокарп хочет восстановить свою ПСП, разместив скобки на нечетных позициях. Но поскольку восстановленная ПСП может быть не уникальной, он хочет выбрать ПСП с минимальной стоимостью. Эта задача слишком сложна для Монокарпа, поэтому можете ли вы помочь ему?

Напоминание: Правильная скобочная последовательность — это строка, состоящая только из скобок, такая что эта строка, когда в неё вставляются 1-ы и +-ы, дает корректное математическое выражение. Например, (), (()) или (()())() являются ПСП, в то время как ), ()( или ())(() — не являются.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следуют сами $$$t$$$ наборов.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n$$$ — четное) — длина строки $$$s$$$.

Во второй строке каждого набора задана строка $$$s$$$ длины $$$n$$$, где все символы на нечетных позициях равны '_' и все символы на четных позициях равны либо '(', либо ')'.

Дополнительные ограничения:

  • из $$$s$$$ можно восстановить как минимум одну правильную скобочную последовательность;
  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Выходные данные

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

Пример
Входные данные
4
6
_(_)_)
2
_)
8
_)_)_)_)
8
_(_)_(_)
Выходные данные
5
1
4
8
Примечание

В первом наборе оптимально сделать $$$s$$$ равной (())(). Стоимость $$$s$$$ будет равна $$$3 + 1 + 1 = 5$$$.

Во втором наборе единственный вариант — сделать $$$s$$$ равной () со стоимостью $$$1$$$.

В третьем наборе единственная возможная ПСП — ()()()() со стоимостью $$$1 + 1 + 1 + 1 = 4$$$.

В четвертом наборе оптимально сделать $$$s$$$ равной (())(()) со стоимостью $$$3 + 1 + 3 + 1 = 8$$$.