1346: 括号配对
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：56
解决：34
题目描述
给出一串长度为n的括号序列（只包含小括号），计算出最少的交换（两两交换）次数，使整个括号序列匹配。
我们认为一个括号匹配，即对任意一个')'，在其左侧都有一个'('与它匹配，且他们形成一一映射关系。
我们认为一个括号匹配，即对任意一个')'，在其左侧都有一个'('与它匹配，且他们形成一一映射关系。
输入
第一行：一个整数T，表示测试实例个数
对于每组测试实例：
第一行：整数n（0≤n≤5×10^6 ），表示括号序列长度
第二行：一个字符串，表示括号
输出
每组测试实例输出一行：包含一个整数 ,表示最少的交换次数
样例输入 复制
2
6
(()))(
6
)))(((样例输出 复制
1
2