← 返回题目列表

Codeforces · 1821/E

E. 重新排列括号

中文机器翻译题面 查看原题

正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如:

- 括号序列“()()”和“(())”是正则表达式(结果表达式为:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。

您将获得一个常规的括号序列。您可以一次性删除一对相邻的括号,使左侧的括号为左括号,右侧的括号为右括号。然后在不改变顺序的情况下连接结果部分。这一举动的成本是这对右括号右侧的括号数量。

常规括号序列的成本是使序列变空所需的移动的最小总成本。

实际上,您没有删除任何括号。相反,您会得到一个常规括号序列和一个整数 $$$k$$$。您最多可以执行 $$$k$$$ 次以下操作:

- 从序列中提取一些括号并将其插入到任意位置(任意两个括号之间、开头或结尾;可能在之前的同一位置)。

执行完所有操作后,括号顺序必须是规则的。所得常规括号序列的最小可能成本是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$k$$$ ($$$0 \le k \le 5$$$) - 您可以执行的最大操作数。

第二行包含一个非空的常规括号序列,它仅由字符“(”和“)”组成。

所有测试用例的常规括号序列的总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 在对其执行最多 $$$k$$$ 操作后常规括号序列的最小可能成本。

示例

输入 #1

7
0
()
0
(())
1
(())
5
()
1
(()()(()))
2
((())()(()())((())))
3
((())()(()())((())))

输出 #1

0
1
0
0
1
4
2