解题思路

设一个括号序列是平衡的，当且仅当满足：

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

等价地说，一个括号序列平衡，当且仅当：

题目内容

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

1)空串是平衡的；

2)若字符串 $A$ 是平衡的，则 “$(A)$” 是平衡的；

3)若字符串 $A$ 与 $B$ 均是平衡的，则 "$AB$” 是平衡的(表示连接)。

例如：括号序列 $()()$ 与 $(())$ 是平衡的：而 $)、)(、($不是。

给定一个偶数长度的括号序列s(仅包含(与))。你可以进行若干次如下操作:

选择一个位置：$(1≤i≤n)$，交换相邻的两个字符 $s_i$ 与 $s_{i+1}$ 。

请你计算，最少需要进行多少次这样的相邻交换，才能使整个序列变为一个平衡的括号序列。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≤T≤10^5)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个偶数 $n(2≤n≤2×10^5)$；

第二行输入一个长度为 $n$ 的字符串 $s$ 仅包含 $’(‘$ 与 $')')$ 。

保证所有测试中 $n$ 的总和不超过 $2×10^5$ ，保证每组数据一定可以通过相邻交换变为平衡序列。

输出描述

对于每组测试数据，输出一行一个整数，表示将s变为平衡括号序列所需的最少相邻交换次数。

样例1

输入

3
2
)(
4
()()
4
))((

输出

1
0
3