重排括号

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个非空正规括号序列。一次删除操作可删除相邻的 () 并拼接剩余部分，代价为被删右括号右侧剩余字符数；序列代价是把它删空所需的最小总代价。

你最多可进行 $k$ 次重排操作：取出一个括号并插入任意位置。最终序列仍须正规。求能得到的最小序列代价。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $k$，第二行包含一个非空正规括号序列。所有序列总长度不超过 $2\cdot10^5$。

输出格式

对每组输出一个整数。

样例输入 1

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

样例输出 1

0
1
0
0
1
4
2

数据范围

• $1\le t\le10^4$，$0\le k\le5$；
• 输入是非空正规括号序列；
• 所有测试组的字符串总长度不超过 $2\cdot10^5$。