[Solution] Jatayu’s Balanced Bracket Sequence solution codeforces

Jatayu’s Balanced Bracket Sequence solution codeforces – Last summer, Feluda gifted Lalmohan-Babu a balanced bracket sequence 𝑠s of length 2𝑛2n.

[Solution] Jatayu’s Balanced Bracket Sequence solution codeforces

Topshe was bored during his summer vacations, and hence he decided to draw an undirected graph of 2𝑛2n vertices using the balanced bracket sequence 𝑠s. For any two distinct vertices 𝑖i and 𝑗j (1𝑖<𝑗2𝑛1≤i<j≤2n), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment 𝑠[𝑖𝑗]s[i…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.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛1051≤n≤105) — the number of opening brackets in string 𝑠s.

The second line of each test case contains a string 𝑠s of length 2𝑛2n — 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 105105.

[Solution] Jatayu’s Balanced Bracket Sequence solution codeforces

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

Example
input

Copy
4
1
()
3
()(())
3
((()))
4
(())(())
output

Copy
1
2
3
3


[Solution] Jatayu’s Balanced Bracket Sequence solution codeforces

Sample explanation:

In the first test case, the graph constructed from the bracket sequence (), is just a graph containing nodes 11 and 22 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):

[Solution] Jatayu’s Balanced Bracket Sequence solution codeforces

• A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters ++ and 11. For example, sequences (())()(), and (()(())) are balanced, while )(((), and (()))( are not.
• The subsegment 𝑠[𝑙𝑟]s[l…r] denotes the sequence [𝑠𝑙,𝑠𝑙+1,,𝑠𝑟][sl,sl+1,…,sr].
• 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.