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。