题目内容

我们称一个仅由左标 ( 和右标 ) 组成的字符串为“和谐标记串”，当且仅当它满足：

• 空串是和谐标记串；
• 如果字符串 $A$ 是和谐标记串，那么左标 ( + $A$ + 右标 ) 也是和谐标记串；
• 如果字符串 $A$ 和 $B$ 都是和谐标记串，那么 $A$ 与 $B$ 拼接得到的字符串也是和谐标记串。

给定一个长度为偶数 $n$ 的字符串 $s$，仅由左标 ( 和右标 ) 组成。你可以进行任意次相邻交换操作：选择位置 $i$（$1 \le i \le n$），交换 $s_i$ 和 $s_{i+1}$。求最少次数使 $s$ 变为和谐标记串。

数据范围：测试数据组数不超过 10^5；字符串长度 $n$ 为偶数且满足 $2 \le n \le 2 \times 10^5$；所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。输入保证每组数据都能通过若干次相邻交换变为和谐标记串。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 T，表示测试数据组数。接下来每组测试数据包含两行：第一行输入一个偶数 n，表示字符串长度；第二行输入一个长度为 n 的字符串 s，仅包含左标 ( 和右标 )。保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$，且每组数据都能通过相邻交换变为和谐标记串。

输出描述

对于每组测试数据，输出一行一个整数，表示将 s 变为和谐标记串所需的最少相邻交换次数。

样例1

输入

1
2
()

输出

0

说明

输入只有 1 组，长度为 2 的串 (). 它本身已经是和谐标记串，可由空串外加一对括号得到。因此不需要任何相邻交换，最少交换次数为 0。

样例2

输入

2
4
)()(
4
)(()

输出

2
1

说明

第 1 组，串为 )()(。扫描过程中：第 1 个右括号使未匹配右括号数变为 1；遇到第 1 个左括号时，它需要跨过前面的 1 个右括号，交换 1 次；第 2 个右括号又使未匹配数变为 1；最后一个左括号再跨过 1 个右括号，交换 1 次，总次数为 $1+1=2$。

第 2 组，串为 )(()。第 1 个右括号先造成未匹配数 1；第 1 个左括号跨过它交换 1 次后，剩余部分 () 已经平衡，因此总次数为 1。

样例3

输入

2
6
)))(((
6
())()(

输出

6
2

说明

第 1 组，串为 )))(((。前 3 个右括号使未匹配数依次变为 1、2、3。之后第 1 个左括号需要跨过 3 个右括号，交换 3 次；第 2 个左括号跨过剩余 2 个，交换 2 次；第 3 个左括号跨过剩余 1 个，交换 1 次，总次数为 $3+2+1=6$。

第 2 组，串为 ())()(。第 3 个字符 ) 使未匹配数变为 1；第 4 个字符 ( 跨过它交换 1 次；第 5 个字符 ) 又使未匹配数变为 1；第 6 个字符 ( 再跨过它交换 1 次，总次数为 $1+1=2$。