CF2196D Double Bracket Sequence

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.

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 $

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

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