A115473.更优括号子序列

给定一个长度为偶数的合法括号序列 $s$。

我们定义：括号序列 $a$ 比括号序列 $b$ 更优，当且仅当满足下面任一条件：

• $b$ 是 $a$ 的真前缀；
• 否则，设两者第一次不同的位置为 $i$，若 $a_i='('$ 且 $b_i=')'$，则认为 $a$ 更优。

现在你需要从 $s$ 中删除若干个字符（至少保留一个字符，且保留下来的相对顺序不能改变），得到一个非空子序列 $t$。要求：

• $t$ 本身也必须是合法括号序列；
• $t$ 比原串 $s$ 更优。

请求出满足条件的 $t$ 的最大可能长度；若不存在这样的 $t$，输出 $-1$。

第一行一个整数 $t$，表示测试组数。

对于每组数据：

• 第一行一个整数 $n$，表示串长；
• 第二行一个长度为 $n$ 的括号串 $s$。

保证给定的 $s$ 一定是合法括号序列。

对每组数据输出一个整数，表示答案；若不存在则输出 $-1$。

数据范围

• $1 \le t \le 10^4$
• $2 \le n \le 2\times 10^5$
• $n$ 为偶数
• 所有测试组的 $n$ 之和不超过 $2\times 10^5$