310359: CF1821E. Rearrange Brackets

E. Rearrange Bracketstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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$.

Output

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.

ExampleInput

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

Output

0
1
0
0
1
4
2

题目大意：
给定一个合法的括号序列，你可以进行以下操作：选择一个括号并将其插入到序列中的任意位置（两个括号之间，序列的开始或结束，甚至可以插回原来的位置）。每次操作后，序列仍需保持合法。操作次数有限，求操作后序列的最小代价，使得序列为空。代价定义为移除相邻括号对的成本，即右括号右侧的括号数量。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数 k（0 ≤ k ≤ 5），表示最大操作次数。
- 第二行包含一个非空的合法括号序列，仅由字符 '(' 和 ')' 组成。
- 所有测试用例的括号序列总长度不超过 2 × 10^5。

输出：
- 对于每个测试用例，输出一行，包含一个整数，表示经过最多 k 次操作后，括号序列的最小代价。

示例输入输出：
输入：
```
7
0
()
0
(())
1
(())
5
()
1
(()()(()))
2
((())()(()())((())))
3
((())()(()())((())))
```
输出：
```
0
1
0
0
1
4
2
```题目大意： 给定一个合法的括号序列，你可以进行以下操作：选择一个括号并将其插入到序列中的任意位置（两个括号之间，序列的开始或结束，甚至可以插回原来的位置）。每次操作后，序列仍需保持合法。操作次数有限，求操作后序列的最小代价，使得序列为空。代价定义为移除相邻括号对的成本，即右括号右侧的括号数量。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数 k（0 ≤ k ≤ 5），表示最大操作次数。 - 第二行包含一个非空的合法括号序列，仅由字符 '(' 和 ')' 组成。 - 所有测试用例的括号序列总长度不超过 2 × 10^5。 输出： - 对于每个测试用例，输出一行，包含一个整数，表示经过最多 k 次操作后，括号序列的最小代价。 示例输入输出： 输入： ``` 7 0 () 0 (()) 1 (()) 5 () 1 (()()(())) 2 ((())()(()())((()))) 3 ((())()(()())((()))) ``` 输出： ``` 0 1 0 0 1 4 2 ```