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.

给定一个长度为偶数的字符串 $s$，由字符 "("、")"、"[" 和 "]" 组成，它们是两种类型的括号（圆括号和方括号）。

我们称一个字符串 $t$ 是优美的，当且仅当它同时满足以下两个条件：

• 所有圆括号构成的子序列是一个合法括号序列$^{\text{∗}}$；
• 所有方括号构成的子序列是一个合法括号序列。

例如，字符串 "[(][)[]]()" 是优美的：其中所有圆括号构成的子序列 "()()" 是一个合法括号序列，而所有方括号构成的子序列 "[][[]]" 也是一个合法括号序列。

你希望将 $s$ 变为某个优美的字符串；为此，你可以执行若干次修改操作：每次操作中，你可以选择一个位置 $i$（满足 $1 \le i \le n$），并将 $s_i$ 修改为任意一个圆括号或方括号。

问：将 $s$ 变为某个优美字符串所需的最少操作次数是多少？

$^{\text{∗}}$一个括号序列被称为合法的，是指可以在其中插入符号 "+" 和 "1"，从而得到一个合法的数学表达式。例如，序列 "(())()"、"[]" 和 "(()(()))" 是合法的，而 ")("、"[[]" 和 "(()))(" 则不是。

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$

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^{5}$）—— 字符串 $s$ 的长度。保证 $n$ 为偶数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，其字符仅由 "("、")"、"[" 和 "]" 组成。

保证所有测试用例中 $n$ 的总和不超过 $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 "[]".

在第一个测试用例中，从字符串 $s$ 出发，通过修改第二个字符，可以得到 "[]"。

在第二个测试用例中，从字符串 $s$ 出发，经过 $2$ 次操作，可以通过修改位置 $2$ 和 $4$ 处的字符，得到 "[][]"。

在第三个测试用例中，从字符串 $s$ 出发，经过 $2$ 次操作，可以通过修改位置 $1$ 和 $4$ 处的字符，得到 "()[]"。

在第四个测试用例中，$s$ 本身已是优美的，因为它可以被划分为子序列 "()" 和 "[]"。