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*;
• 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?

*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 Specification

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 Specification

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

Examples

Example Input 1

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

Source

Codeforces