在此问题中,两个字符串 $$$T$$$ 和 $$$U$$$ 的串联由 $$$T+U$$$ 表示。
仅由括号组成的字符串(左括号 '(' 或右括号 ')') 是 平衡 当且仅当它是以下之一。
- 空字符串。
- 两个非空平衡字符串的串联。
- 连接 $$$\texttt{(} + T + \texttt{)}$$$,其中 $$$T$$$ 是平衡字符串。
字符串是 变形 当且仅当它是以下之一。
- 字符串“)".
- 连接 $$$T + \texttt{)} + U$$$,其中 $$$T$$$ 和 $$$U$$$ 是变形字符串。
- 连接 $$$\texttt{(} + T + \texttt{(}$$$,其中 $$$T$$$ 是变形字符串。
字符串 $$$T$$$ 平衡变形 如果 $$$T$$$ 变形并且串联 $$$T + \texttt{)}$$$ 平衡。例如,字符串“()(“平衡变形。
给定一个字符串 $$$S$$$,长度为 $$$n$$$,仅由括号组成。在给定的输入约束下,可以证明存在字符串 $$$X$$$ 和 $$$Y$$$,使得串联 $$$X + S + Y$$$ 具有变形平衡。确定 $$$|X| 的最小可能值+ |Y|$$$($$$X$$$ 和 $$$Y$$$ 的长度之和)。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) 表示测试用例的数量。之后,$$$t$$$ 测试用例如下。它们各自介绍如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。
第二行包含长度为 $$$n$$$ 的字符串 $$$S$$$,仅包含 '(' 或 ')'.
一个输入文件中所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出 $$$|X|+|Y|$$$ 的最小可能值,使得串联 $$$X + S + Y$$$ 具有变形平衡。
示例
输入复制
3 3 ()( 1 ) 7 (())())
输出复制
0 2 4
注意
示例输入/输出#1 的说明
对于第一个测试用例,给定的弦已经具有变形的平衡。
对于第二个测试用例,将 $$$X$$$ 和 $$$Y$$$ 设置为“(“产生串联”()(”,其平衡变形。$$$|X|+|Y|$$$ 的值为 $$$2$$$。
对于第三个测试用例,只需将 $$$X$$$ 设置为“((()" 和 $$$Y$$$ 为空字符串以获得 $$$|X|+|Y|$$$ 的最小值。