E. Скобочная стоимость
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Деймон Таргариен решил перестать быть похожим на персонажа Metin2. Он превратил себя в прекраснейшую вещь — скобочную последовательность.

Для последовательности скобок мы можем выполнять два вида операций:

  • Выберите одну из её подстрок$$$^\dagger$$$ и циклически сдвиньте её вправо. Например, после циклического сдвига вправо «(())» станет «)(()»;
  • Вставьте любую скобку, открывающую «(» или закрывающую «)», в любом месте последовательности.

Мы определяем стоимость скобочной последовательности как минимальное количество таких операций, чтобы сделать её правильной$$$^\ddagger$$$.

Для заданной скобочной последовательности $$$s$$$ длины $$$n$$$ найдите сумму стоимостей всех $$$\frac{n(n+1)}{2}$$$ её непустых подстрок. Обратите внимание, что для каждой подстроки мы вычисляем стоимость независимо.

$$$^\dagger$$$ Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

$$$^\ddagger$$$ Последовательность скобок называется правильной, если её можно превратить в правильное математическое выражение, добавив символы $$$+$$$ и $$$1$$$. Например, последовательности «(())()», «()» и «(()(()))» правильные, в то время как «)(», «(()» и «(()))(» не являются правильными.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину скобочной последовательности.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
1
)
4
)()(
3
())
5
(((((
10
)(())))())
Выходные данные
1
9
6
35
112
Примечание

В первом наборе входных данных есть единственная подстрока «)». Её стоимость $$$1$$$, потому что мы можем вставить «(» в начало этой подстроки и получить строку «()», то есть сбалансированную строку.

Во втором наборе входных данных стоимость каждой подстроки длины один равна $$$1$$$. Стоимость подстроки «)(» равна $$$1$$$, потому что мы можем циклически сдвинуть ее вправо и получить строку «()». Стоимость строк « )()» и «()(» равна $$$1$$$, потому что достаточно вставить по одной скобке в каждую из них. Стоимость подстроки «)()(» равна $$$1$$$, потому что мы можем циклически сдвинуть её вправо и получить строку «()()». Таким образом, есть $$$4 + 2 + 2 + 1 = 9$$$ подстрока стоимостью $$$1$$$ и $$$1$$$ подстрока из стоимостью $$$0$$$. Таким образом, сумма стоимостей равна $$$9$$$.

В третьем наборе входных данных:

  • «(», стоимость равна $$$1$$$;
  • «()», стоимость равна $$$0$$$;
  • «())», стоимость равна $$$1$$$;
  • «)», стоимость равна $$$1$$$;
  • «))», стоимость равна $$$2$$$;
  • «)», стоимость равна $$$1$$$.

Таким образом, сумма стоимостей равна $$$6$$$.