D. Double Bracket Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ of even length, consisting of the characters "(", ")", "[" and "]", which are brackets of two types (round and square).

We call a string $$$t$$$ beautiful if it satisfies two conditions simultaneously:

  • The subsequence of all round brackets forms a correct bracket sequence$$$^{\text{∗}}$$$;
  • The subsequence of all square brackets forms a correct bracket sequence.

For example, the string "[(][)[]]()" is beautiful, as the subsequence of all round brackets in it "()()" forms a correct bracket sequence and the subsequence of all square brackets in it "[][[]]" forms a correct bracket sequence.

You would like to turn $$$s$$$ into any beautiful string; for this, you can change the characters: in one operation, you can choose a position $$$i$$$, such that $$$1 \le i \le n$$$ and change the character $$$s_{i}$$$ to any round or square bracket.

What is the minimum number of operations required to transform $$$s$$$ into any beautiful string?

$$$^{\text{∗}}$$$A bracket sequence is called correct if by inserting the symbols "+" and "1" into it, one can obtain a valid mathematical expression. For example, the sequences "(())()", "[]" and "(()(()))" are correct, while ")(", "[[]" and "(()))(" are not.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — the length of the string $$$s$$$. It is guaranteed that $$$n$$$ is even.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting only of the characters "(", ")", "[" and "]".

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$

Output

For each test case, output a single integer — the answer to the problem.

Example
Input
5
2
[)
4
[)[(
4
))[[
4
([)]
6
[)]](]
Output
1
2
2
0
2
Note

In the first test case, from $$$s$$$ you can obtain "[]" by changing the second character.

In the second test case, from $$$s$$$, in $$$2$$$ operations, you can obtain "[][]", by changing the characters at positions $$$2$$$ and $$$4$$$.

In the third test case, from $$$s$$$, in $$$2$$$ operations, you can obtain "()[]", by changing the characters at positions $$$1$$$ and $$$4$$$.

In the fourth test case, $$$s$$$ is already beautiful, as it can be divided into the subsequences "()" and "[]".