Once OC received a challenge from his memory fragments, which aroused his curiosity:
"You are given one bracket sequence $$$s$$$ with length $$$n$$$, answer the minimum operations you need to make all non-empty subsequences$$$^\dagger$$$ imbalanced$$$^\ddagger$$$.
Define that your one operation is to select $$$i \in [1, n]$$$ and change $$$s_i$$$ to another bracket."
But he is too busy beating the deadline, so he asked you to help him.
$$$^\dagger$$$ A sequence $$$b$$$ is a subsequence of sequence $$$a$$$ if $$$b$$$ can be obtained by deleting several (possibly, zero or all) elements from $$$a$$$. For example, $$$(()$$$, $$$()$$$, and $$$())$$$ are some subsequences of $$$()()$$$.
$$$^\ddagger$$$ A sequence is called imbalanced if you cannot turn it into a valid math expression by adding characters $$$+$$$ and $$$1$$$. For example, sequences $$$)($$$, $$$(()$$$, and $$$(()))($$$ are imbalanced, while $$$(())()$$$, $$$()$$$, and $$$(()(()))$$$ are not.
There are multiple test cases. The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, denoting the number of test cases. For each test case:
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10 ^ 5)$$$.
The second line contains a string $$$s$$$ with length $$$n$$$, denoting the given bracket sequence.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.
For each test case, output one line containing one integer $$$x$$$, denoting the minimum operations you need to make all non-empty subsequences imbalanced.
24()))7)()()((
1 2
For the first sample test case, you can perform $$$1$$$ operation on $$$1$$$, changing $$$s$$$ to $$$))))$$$.
For the second sample test case, you can perform $$$2$$$ operations on $$$3, 5$$$, changing $$$s$$$ to $$$)(((((($$$.
These are not the only ways to satisfy the constraints.
| Name |
|---|


