「SiR-1」Bracket

> Everything that kills me makes me feel alive.

Mirika 有一个长度为 $n$ 的括号序列 $s$。 对于一个括号序列 $S$，Mirika 可以执行两种操作： - 变换：选择一个位置 $i$ 满足 $1 \leq i \leq \lvert S \rvert$，使得 $S$ 变为 $S_iS_{i+1}\cdots S_{\lvert S\rvert}S_1S_2\cdots S_{i-2}S_{i-1}$。 - 插入：在这个序列的 **任意位置** 插入一个括号（左右括号均可）。 Mirika 定义括号序列 $S$ 的权值 $f(S)$ 为能将这个括号序列变成一个合法括号序列所需的最小操作数。 其中，合法括号序列的定义为： + 空串为 合法括号序列。 + 若 $\texttt A$ 为 合法括号序列，则 $\texttt{(A)}$ 为 合法括号序列。 + 若 $\texttt A, \texttt B$ 均为 合法括号序列，则 $\texttt{AB}$ 也为 合法括号序列。 现在 Mirika 想要求出： $\sum_{l=1}^n \sum_{r=l}^n f(s[l,r])$ 其中 $s[l,r]$ 表示由 $s_l,s_{l+1},\cdots,s_r$ 形成的连续子序列。 但是 Mirika 太菜了不会算，于是只好求助于你。

**本题每个测试点内有多组数据。** 第一行一个正整数 $T$ 表示测试数据组数。 对于每组数据，第一行一个正整数 $n$。 第二行一个长度为 $n$ 的括号序列 $s$。

输出共 $T$ 行，第 $i$ 行一个整数表示第 $i$ 组测试数据的答案。

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

4
11
16
12
241

### 样例解释 对于 $s = \texttt{())(}$： + 考虑 $s[1,4]=\texttt{())(}$。执行变换操作 $i=4$，有 $\texttt{())(} \Rightarrow \texttt{(())}$，其中 $\texttt{(())}$ 是合法括号序列，故 $f(s[1, 4]) = 1$。可以证明不存在更优的策略。 + 考虑 $s[2,4]=\texttt{))(}$。执行变换操作 $i=2$，再在序列开头插入一个左括号，有 $\texttt{))(} \Rightarrow \texttt{)()} \Rightarrow \texttt{()()}$，其中 $\texttt{()()}$ 是合法括号序列，故 $f(s[2, 4]) = 2$。可以证明不存在更优的策略。 ### 数据规模与约定 **本题采用捆绑测试。** + 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$ 内不含有右括号。 + Subtask 3（10 pts）：对于所有整数 $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）：无特殊限制。 对于所有数据，$1 \leq T \leq 10000$，$1 \leq n \leq 2 \times 10^6$，$1 \leq \sum n \leq 2 \times 10^7$。