平衡括号最少交换次数

题目描述

我们称一个括号序列是平衡的，当且仅当满足以下递归定义：

• 空串是平衡的；
• 若字符串 A 是平衡的，则 (A) 是平衡的；
• 若字符串 A 与 B 都是平衡的，则 AB 也是平衡的。

现在给定一个只包含 '(' 和 ')' 的偶数长度字符串 s。你可以进行若干次如下操作：

• 选择两个下标 i, j（1 <= i < j <= n），交换 s[i] 与 s[j]。

请计算最少需要交换多少次，才能使整个序列变成一个平衡括号序列。

保证对于每组测试数据，一定存在可行解。

输入格式

第一行输入一个整数 T，表示测试数据组数。

接下来对于每组测试数据：

• 第一行输入一个偶数 n；
• 第二行输入一个长度为 n 的字符串 s。

输出格式

对于每组测试数据，输出一行一个整数，表示最少交换次数。

数据范围

1 <= T <= 10^5

2 <= n <= 2 * 10^5

所有测试数据中 n 的总和不超过 2 * 10^5。

字符串 s 仅由 '(' 和 ')' 组成。

样例

输入

4
2
)(
4
()()
4
))((
8
))))((((

输出

1
0
1
2