正则括号序列是通过在序列的原始字符之间插入字符“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