CF2196D Double Bracket Sequence

给定一个长度为 $s$ 的偶数的字符串，仅包含括号字符 "("、")"、"\[" 和 "\]"，即有两种类型的括号（圆括号和方括号）。 我们称字符串 $t$ 为美丽的，当且仅当它同时满足以下两个条件： - 所有圆括号组成的子序列构成一个合法的括号序列； - 所有方括号组成的子序列构成一个合法的括号序列。 例如，字符串 "\[(\]\[)\[\]\]()" 是美丽的，因为其中所有圆括号组成的子序列 "()()" 是一个合法括号序列，而所有方括号组成的子序列 "\[\]\[\[\]\]" 也是一个合法括号序列。 你希望将 $s$ 变成任意一个美丽的字符串。为此你可以修改字符：每一次操作可以选择一个位置 $i$，$1 \leq i \leq n$，并将 $s_i$ 修改为任意一种圆括号或方括号。 将 $s$ 转换成任意一个美丽的字符串，最少需要多少步操作？ $^{\text{∗}}$ 括号序列被称为合法的，当且仅当在其间插入符号 "+" 和 "1"，可以得到一个有效的数学表达式。例如，"(()())"、"\[\]" 和 "(()(()))" 是合法的，而 ")("、"\[\[\]" 和 "(()))(" 不是。

每组输入包含多组测试用例。第一行包含测试用例数量 $t$（$1 \leq t \leq 10^4$）。接下来为每组测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$），表示字符串 $s$ 的长度。保证 $n$ 是偶数。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅包含括号字符 "("、")"、"\[" 和 "\]"。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示将 $s$ 变为美丽字符串所需的最少操作次数。

在第一个测试用例中，可以通过将第二个字符修改为 "]"，使 $s$ 变为 "\[\]"。 在第二个测试用例中，可以通过修改第 $2$ 个和第 $4$ 个字符，使 $s$ 变为 "\[\]\[\]"，共需要 $2$ 次操作。 在第三个测试用例中，可以通过修改第 $1$ 个和第 $4$ 个字符，使 $s$ 变为 "()\[\]"，共需要 $2$ 次操作。 在第四个测试用例中，$s$ 已经是美丽的，因为它可以被分为子序列 "()" 和 "\[\]"。 由 ChatGPT 5 翻译