A16710 | 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$ 变为美丽字符串所需的最少操作次数。