题意简述

给一个合法括号串 $S$，递归地定义合法括号串：

• $\texttt{()}$ 是合法括号串。
• 若 $\texttt{A}$ 是合法括号串，那么 $\texttt{(A)}$ 是合法括号串。
• 若 $\texttt{A},\texttt{B}$ 均是合法括号串，那么 $\texttt{AB}$ 是合法括号串。

求出 $S$ 的所有非空合法括号子串数量。

输入格式

本题有多组测试数据。

第一行输入两个整数 $sid,T$，表示测试点编号和数据组数。样例中 $sid = 0$。

对于每组测试数据：输入一行字符串 $S$。

输出格式

对于每组测试数据，输出一个整数，表示 $S$ 的合法括号子串数量

样例输入 1

0 3
(()())
((())())
()()(()())

样例输出 1

4
5
9

对于第一组测试数据，合法括号子串有：$S[2,3],S[4,5],S[2,5],S[1,6]$。

更多样例下载

样例4满足测试点 $6\sim 10$ 的限制。

数据范围与约定

对于所有数据，保证$1\leq T \leq 5$ , $1 \le |S| \le 5 \times 10^5$。保证 $S$ 是合法括号串。