CFCF2196D.Double Bracket Sequence

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个长度为 $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$ 变为美丽字符串所需的最少操作次数。

输入#1

5
2
[)
4
[)[(
4
))[[
4
([)]
6
[)]](]

输出#1

在第一个测试用例中，可以通过将第二个字符修改为 "]"，使 $s$ 变为 "[]"。

在第二个测试用例中，可以通过修改第 $2$ 个和第 $4$ 个字符，使 $s$ 变为 "[][]"，共需要 $2$ 次操作。

在第三个测试用例中，可以通过修改第 $1$ 个和第 $4$ 个字符，使 $s$ 变为 "()[]"，共需要 $2$ 次操作。

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