说明

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$。