CF1976D.Invertible Bracket Sequences

我们定义一个合法的括号序列，是仅由 ( 和 ) 构成的字符串且：

1. 空串 $\epsilon$ 是合法的括号序列。
2. 若 $s$ 为合法的括号序列，则 $(s)$ 也为合法的括号序列。
3. 若 $s,t$ 均为合法的括号序列，则 $st$ 也为合法的括号序列。（其中 $st$ 表示将字符串 $s$ 和 $t$ 拼接。）

定义对一个括号序列的翻转操作为：将这个括号序列的所有 ( 变为 )，所有 ) 变为 (。

如 ()((( 翻转后成为 )()))。

给定一个保证合法的字符串 $s$。

你可以选择字符串 $s$ 的一个子串进行翻转操作。（注意是子串，与子序列区分，子串要求连续。）

问翻转了一个子串后得到的字符串 $s'$ 仍然是合法括号序列的方案数。

先是一个数字 $t$ 表示数据组数（$1 \le t \le 10^4$）。

接下来 $t$ 行，每行一个合法括号序列 $s$（$1 \le \sum |s| \le 2\times10^5$）。

对于每组数据，输出一个数字 $x$，表示翻转 $s$ 的一个子串后仍然是合法括号序列的方案数。

在本题中，不可以翻转长度为 $0$ 的子串。

translate by Hoks。