## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Dense Bracket Sequence CodeChef Solution | CodeChef Problem Solution 2022

A bracket sequence $S$ is called dense if one of the following is true:

• $S$ is empty.
• $S=\left(X\right)$ where $X$ is dense.

You are given a bracket sequence $S$. What is the minimum number of brackets you must remove to make it dense?

### Input Format

• The first line of input will contain a single integer $T$, the number of test cases. The description of the $T$ test cases follows.
• The first line of each test case contains one integer $N$, denoting the length of the bracket sequence.

• The second line of each test case contains the bracket sequence $S$ of length $N$.

### Output Format

For each test case, output on a new line the minimum number of brackets you must remove from $S$ to make it dense.

### Constraints

• $1\le T\le 2\cdot {10}^{4}$
• $2\le N\le 3\cdot {10}^{5}$