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.

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 "[]".

#	Name	Rating↕	Solved↕
2196D	Double Bracket Sequence data structures dp expression parsing flows greedy strings	2500	1.1k
552E	Vanya and Brackets brute force dp expression parsing greedy implementation strings	2100	1.8k
70B	Text Messaging expression parsing greedy strings	1600	2.1k

Problemset