Background

Everything that kills me makes me feel alive.

Problem Description

Mirika has a bracket sequence $s$ of length $n$.

For a bracket sequence $S$, Mirika can perform two operations:

• Rotation: choose a position $i$ satisfying $1 \leq i \leq \lvert S \rvert$, and change $S$ into $S_iS_{i+1}\cdots S_{\lvert S\rvert}S_1S_2\cdots S_{i-2}S_{i-1}$.
• Insertion: insert one bracket (either a left bracket or a right bracket) at any position in the sequence.

Mirika defines the weight $f(S)$ of a bracket sequence $S$ as the minimum number of operations needed to turn this bracket sequence into a valid bracket sequence.

The definition of a valid bracket sequence is:

• The empty string is a valid bracket sequence.
• If $\texttt A$ is a valid bracket sequence, then $\texttt{(A)}$ is also a valid bracket sequence.
• If both $\texttt A$ and $\texttt B$ are valid bracket sequences, then $\texttt{AB}$ is also a valid bracket sequence.

Now Mirika wants to compute:

$\sum_{l=1}^n \sum_{r=l}^n f(s[l,r])$

where $s[l,r]$ denotes the contiguous subsequence formed by $s_l,s_{l+1},\cdots,s_r$.

However, Mirika is too weak to compute it, so she has to ask you for help.

Input Format

There are multiple test cases in each test point.

The first line contains a positive integer $T$, denoting the number of test cases.

For each test case, the first line contains a positive integer $n$.

The second line contains a bracket sequence $s$ of length $n$.

Output Format

Output a total of $T$ lines. The $i$-th line contains one integer, denoting the answer for the $i$-th test case.

5
2
((
4
())(
5
()(()
5
()()(
15
()())(())))()()

4
11
16
12
241

Hint

Sample Explanation

For $s = \texttt{())(}$:

• Consider $s[1,4]=\texttt{())(}$. Perform a rotation operation with $i=4$, then $\texttt{())(} \Rightarrow \texttt{(())}$. Since $\texttt{(())}$ is a valid bracket sequence, $f(s[1, 4]) = 1$. It can be proven that there is no better strategy.
• Consider $s[2,4]=\texttt{))(}$. Perform a rotation operation with $i=2$, then insert a left bracket at the beginning of the sequence, then $\texttt{))(} \Rightarrow \texttt{)()} \Rightarrow \texttt{()()}$. Since $\texttt{()()}$ is a valid bracket sequence, $f(s[2, 4]) = 2$. It can be proven that there is no better strategy.

Constraints and Notes

This problem uses bundled test.

• Subtask 0 (15 pts): $n \leq 400$, $\sum n \leq 800$.
• Subtask 1 (20 pts): $n \leq 2\times 10^3$, $\sum n \leq 4\times 10^3$.
• Subtask 2 (5 pts): $s$ contains no right brackets.
• Subtask 3 (10 pts): for all integers $1\le i < n$, $s_i \neq s_{i+1}$.
• Subtask 4 (30 pts): $n \leq 2\times 10^5$, $\sum n \leq 5\times 10^5$.
• Subtask 5 (20 pts): no special constraints.

For all testdata, $1 \leq T \leq 10000$, $1 \leq n \leq 2 \times 10^6$, $1 \leq \sum n \leq 2 \times 10^7$.

Translated by ChatGPT 5