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 太菜了不会算，于是只好求助于你。
## Input
**本题每个测试点内有多组数据。**
第一行一个正整数 $T$ 表示测试数据组数。
对于每组数据，第一行一个正整数 $n$。
第二行一个长度为 $n$ 的括号序列 $s$。
## Output
输出共 $T$ 行，第 $i$ 行一个整数表示第 $i$ 组测试数据的答案。
[samples]
## Background
> Everything that kills me makes me feel alive.
## Note
### 样例解释
对于 $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$。