去年夏天,Feluda 向 Lalmohan-Babu 赠送了长度为 $$$2 n$$$ 的平衡括号序列 $$$s$$$。
Topshe 在暑假期间很无聊,因此他决定使用平衡括号序列 $$$s$$$ 绘制 $$$2 n$$$ 个顶点的无向图。对于任何两个不同的顶点 $$$i$$$ 和 $$$j$$$ ($$$1 \le i < j \le 2 n$$$),当且仅当子段 $$$s[i \ldots j]$$$ 形成平衡的括号序列时,Topshe 在这两个节点之间绘制一条边(无向且未加权)。
确定 Topshe 图中连通分量的数量。
有关下划线术语的定义,请参阅注释部分。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$s$$$ 中左括号的数量。
每个测试用例的第二行包含一个长度为 $$$2 n$$$ 的字符串 $$$s$$$ — 一个平衡的括号序列,由 $$$n$$$ 左括号“(”和 $$$n$$$ 右括号“)”组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - Topshe 图中连接组件的数量。
示例
输入 #1
4 1 () 3 ()(()) 3 ((())) 4 (())(())
输出 #1
1 2 3 3
注意
示例说明:
在第一个测试用例中,从括号序列 () 构造的图只是一个包含由单条边连接的节点 $$$1$$$ 和 $$$2$$$ 的图。
在第二个测试用例中,从括号序列 ()(()) 构造的图如下(包含两个连接的组件):
带下划线的术语的定义:
- 如果可以通过添加字符 $$$+$$$ 和 $$$1$$$ 将括号序列转换为有效的数学表达式,则该序列称为平衡的。例如,序列 (())()、() 和 (()(())) 是平衡的,而 )(、(() 和 (()))( 则不是。
- 子段 $$$s[l \ldots r]$$$ 表示序列 $$$[s_l, s_{l + 1}, \ldots, s_r]$$$。
- 连接组件是一组顶点 $$$X$$$,这样对于该集合中的每两个顶点,图中至少存在一条连接这些顶点的路径,但向 $$$X$$$ 添加任何其他顶点会违反此规则。