CF1726C.Jatayu's Balanced Bracket Sequence

Last summer, Feluda gifted Lalmohan-Babu a balanced bracket sequence $s$ of length $2 n$.

Topshe was bored during his summer vacations, and hence he decided to draw an undirected graph of $2 n$ vertices using the balanced bracket sequence $s$. For any two distinct vertices $i$ and $j$ ($1 \le i \lt j \le 2 n$), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment $s[i \ldots j]$ forms a balanced bracket sequence.

Determine the number of connected components in Topshe's graph.

See the Notes section for definitions of the underlined terms.

去年夏天，Feluda 送给拉尔莫汉·巴布一个长度为 $2n$ 的平衡括号序列 $s$。

托普希在暑假期间感到无聊，于是决定用这个平衡括号序列 $s$ 构造一个包含 $2n$ 个顶点的无向图。对于任意两个不同的顶点 $i$ 和 $j$（其中 $1 \le i \lt j \le 2n$），托普希当且仅当子段 $s[i \ldots j]$ 构成一个平衡括号序列时，在这两个顶点之间连一条边（无向、无权）。

请确定托普希所构造的图中连通分量的个数。

有关下划线术语的定义，请参见“注释”部分。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of opening brackets in string $s$.

The second line of each test case contains a string $s$ of length $2 n$ — a balanced bracket sequence consisting of $n$ opening brackets "(", and $n$ closing brackets ")".

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示字符串 $s$ 中左括号的数量。

每个测试用例的第二行包含一个长度为 $2n$ 的字符串 $s$，它是一个由 $n$ 个左括号 "(" 和 $n$ 个右括号 ")" 构成的平衡括号序列。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, output a single integer — the number of connected components in Topshe's graph.

对于每个测试用例，输出一个整数——Topshe 图中连通分量的数量。

Sample explanation:

In the first test case, the graph constructed from the bracket sequence (), is just a graph containing nodes $1$ and $2$ connected by a single edge.

In the second test case, the graph constructed from the bracket sequence ()(()) would be the following (containing two connected components):

Definition of Underlined Terms:

• A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $+$ and $1$. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.
• The subsegment $s[l \ldots r]$ denotes the sequence $[s_l, s_{l + 1}, \ldots, s_r]$.
• A connected component is a set of vertices $X$ such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to $X$ violates this rule.

样例解释：

在第一个测试用例中，由括号序列 (), 构造出的图仅包含节点 $1$ 和 $2$，且二者通过一条边相连。

在第二个测试用例中，由括号序列 ()(()) 构造出的图如下所示（包含两个连通分量）：

下划线术语定义：

• 若一个括号序列可通过添加字符 $+$ 和 $1$ 转化为合法的数学表达式，则称该括号序列为平衡的。例如，序列 (())(), (), 和 (()(())) 是平衡的，而 )(, ((), 和 (()))( 则不是。
• 子段 $s[l \ldots r]$ 表示序列 $[s_l, s_{l + 1}, \ldots, s_r]$。
• 连通分量是指一个顶点集合 $X$，使得该集合中任意两个顶点之间均至少存在一条图中的路径相连，但向 $X$ 中添加任一其他顶点都会破坏这一性质。