[Solution] Jatayu's Balanced Bracket Sequence Codeforces Solution

C. Jatayu's Balanced Bracket Sequence

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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\le i<j\le 2n$), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment 𝑠[𝑖…𝑗]$s[i\dots 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≤𝑡≤105$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≤𝑛≤105$1\le n\le {10}^5$) — the number of opening brackets in string 𝑠$s$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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 105${10}^5$.

Output

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