括号序列操作专家

题号：NC253619
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

氧气少年有一个长度为 $n$ 的括号序列，括号序列只包含左括号 ` $\tt ($ ' 和右括号 ` $\tt )$ '。

一个括号序列是合法的，当且仅当此括号序列可以通过插入加号 ` $\tt +$ ' 和数字 $1$ 得到一个正确的算术表达式。例如：括号序列 $\tt (())()$ ， $\tt ()$ ，和 $\tt (()(()))$ 都是合法的，而 $\tt )($ ， $\tt (()$ 和 $\tt (()))($ 不是合法的。

氧气少年的括号序列不一定是合法的。

月色哥哥是一个括号序列的操作专家，他的任务是帮助氧气少年把这个括号序列变成一个合法的序列。

为了把这个括号序列变合法，月色哥哥每次可以进行下面的操作：

交换任意两个相邻括号。

如果无论月色哥哥怎么操作都无法使括号序列变合法，输出 $-1$ ；否则请输出他需要做的最少的操作次数。

输入描述:

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

第一行包含一个整数 ，表示括号序列的长度。

第二行包含一个长度为  的字符串，表示该括号序列。保证字符串只包含左括号 `' 和右括号 `'。

保证对于所有的测试用例， 的总和不超过 。

输出描述:

对于每组测试用例：

仅输出一行，包含一个整数。如果无论怎么操作都无法使括号序列变合法，输出 ；否则请输出他需要做的最少的操作次数。

示例1

输入

复制

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

输出

复制

1
-1
17