CF1821E.Rearrange Brackets

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

• bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
• bracket sequences ")(", "(" and ")" are not.

You are given a regular bracket sequence. In one move, you can remove a pair of adjacent brackets such that the left one is an opening bracket and the right one is a closing bracket. Then concatenate the resulting parts without changing the order. The cost of this move is the number of brackets to the right of the right bracket of this pair.

The cost of the regular bracket sequence is the smallest total cost of the moves required to make the sequence empty.

Actually, you are not removing any brackets. Instead, you are given a regular bracket sequence and an integer $k$. You can perform the following operation at most $k$ times:

• extract some bracket from the sequence and insert it back at any position (between any two brackets, at the start or at the end; possibly, at the same place it was before).

After all operations are performed, the bracket sequence has to be regular. What is the smallest possible cost of the resulting regular bracket sequence?

正则括号序列是指：通过在原序列的字符之间插入字符 "1" 和 "+"，可以将其转化为一个合法的算术表达式。例如：

• 括号序列 "()()" 和 "(())" 是正则的（对应得到的表达式分别为 "(1)+(1)" 和 "((1+1)+1)"）；
• 括号序列 ")(", "(" 和 ")" 则不是正则的。

你被给定一个正则括号序列。一次操作定义为：移除一对相邻的括号，其中左侧为左括号 (，右侧为右括号 )；然后将剩余部分按原顺序拼接起来。该操作的代价等于该右括号右侧的括号总数。

一个正则括号序列的代价，是指将其清空所需的若干次操作的总代价的最小值。

实际上，你并不真正移除任何括号。相反，你被给定一个正则括号序列和一个整数 $k$。你最多可执行以下操作 $k$ 次：

• 从序列中取出某个括号，并将其重新插入到任意位置（即任意两个括号之间、开头或结尾；甚至可以插回原来的位置）。

所有操作完成后，所得括号序列仍需是正则的。问：最终所得正则括号序列的最小可能代价是多少？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $k$ ($0 \le k \le 5$) — the maximum number of operations you can perform.

The second line contains a non-empty regular bracket sequence, it consists only of characters '(' and ')'.

The total length of the regular bracket sequences over all testcases doesn't exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含一个整数 $k$（$0 \le k \le 5$）—— 你最多可执行的操作次数。

每个测试用例的第二行包含一个非空的合法括号序列，该序列仅由字符 '(' 和 ')' 组成。

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

For each testcase, print a single integer — the smallest possible cost of the regular bracket sequence after you perform at most $k$ operations on it.

对于每个测试用例，输出一个整数——在对该括号序列最多执行 $k$ 次操作后，所能得到的合法括号序列的最小可能代价。