在本题中，两个字符串 $T$ 和 $U$ 的拼接记作 $T + U$。

一个仅由括号（左括号 ( 或右括号 )）组成的字符串是平衡的（balanced），当且仅当它满足以下条件之一：

• 空字符串。
• 两个非空平衡字符串的拼接。
• 拼接字符串 ( + $T$ + )，其中 $T$ 是一个平衡字符串。

例如，() 和 (())() 是平衡的，而 ()( 和 ((() 则不是。

一个字符串是变形的（deformed），当且仅当它满足以下条件之一：

• 字符串 )。
• 拼接字符串 $T$ + ) + $U$，其中 $T$ 和 $U$ 都是变形字符串。
• 拼接字符串 ( + $T$ + (，其中 $T$ 是一个变形字符串。

例如，()( 和 ))()( 是变形的，而 () 和 (() 则不是。

如果一个字符串 $T$ 是变形的，且拼接字符串 $T$ + ) 是平衡的，则称字符串 $T$ 具有变形平衡（deformed balance）。例如，字符串 ()( 具有变形平衡。

给定一个长度为 $n$ 且仅由括号组成的字符串 $S$。在给定的输入限制下，可以证明一定存在字符串 $X$ 和 $Y$，使得拼接后的字符串 $X + S + Y$ 具有变形平衡。请确定 $|X| + |Y|$（$X$ 和 $Y$ 的长度之和）的最小可能值。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)，表示测试数据的组数。接下来是 $t$ 组测试数据，每组数据的格式如下：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。

第二行包含一个长度为 $n$ 的字符串 $S$，仅由 ( 或 ) 组成。

在一个输入文件中，所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出 $|X| + |Y|$ 的最小可能值，使得拼接后的字符串 $X + S + Y$ 具有变形平衡。

样例

输入样例 1

3
3
()(
1
)
7
(())())

输出样例 1

0
2
4

说明

对于第一组测试数据，给定的字符串已经具有变形平衡。

对于第二组测试数据，将 $X$ 和 $Y$ 都设为 (，可以得到拼接后的字符串 ()(，它具有变形平衡。$|X| + |Y|$ 的值为 $2$。

对于第三组测试数据，只需将 $X$ 设为 ((()，将 $Y$ 设为空字符串，即可达到 $|X| + |Y|$ 的最小值 $4$。