Yuki 发现回文括号序列不一定是合法括号序列，因此她设计了另一种方式来定义回文合法括号序列。
Yuki 根据以下规则定义回文括号序列：
- 空字符串是回文括号序列。
(和)是回文括号序列。- 如果括号序列 $s$ 是回文括号序列，那么
(s(和)s)也是回文括号序列。
Yuki 根据以下规则定义合法括号序列：
- 空字符串是合法括号序列。
- 如果括号序列 $s$ 是合法括号序列，那么
(s)是合法括号序列。 - 如果括号序列 $s$ 和 $t$ 都是合法括号序列，那么 $st$（两个括号序列的拼接）也是合法括号序列。
对于一个括号序列 $s = s_1 \dots s_n$，Yuki 定义 $s$ 是回文合法括号序列当且仅当：
- $s_2 \dots s_{n-1}$ 是回文括号序列。
- $s_1 \dots s_n$ 是合法括号序列。
特别地，空字符串和 () 也是回文合法括号序列。
例如，(())() 和 ()()(()()) 是回文合法括号序列，而 ((())) 和 ()()(()) 不是。
现在，Yuki 有一个长度为 $n$ 的括号序列 $s$，她想找到 $s$ 的最长子序列$^*$，使得该子序列是一个回文合法括号序列。然而，Yuki 不知道该怎么做，所以你需要帮助她求出最长此类子序列的长度。
$^*$：序列 $a$ 是序列 $b$ 的子序列当且仅当 $a$ 可以通过从 $b$ 中删除零个或多个元素获得；特别地，空序列是任何序列的子序列。
输入格式
本题包含多个测试用例。
第一行包含一个正整数 $t$ ($1 \le t \le 5000$)，表示测试用例的数量。
对于每个测试用例：
- 第一行包含一个正整数 $n$ ($1 \le n \le 5000$)。
- 第二行包含一个长度为 $n$ 的括号序列 $s$ ($s_i \in \{(, )\}$)。
保证所有测试用例中 $n$ 的总和不超过 $10^4$。
输出格式
对于每个测试用例，输出一行，包含一个整数，表示满足条件的最长子序列的长度。
样例
输入样例 1
3 5 (()(( 7 )))(((( 8 ())(()()
输出样例 1
2 0 6
说明
对于第一个测试用例：
- 满足条件的最长子序列为 $s_1s_3 = ()$ 和 $s_2s_3 = ()$，因此答案为 $2$。
对于第二个测试用例：
- 满足条件的最长子序列为空字符串，因此答案为 $0$。
对于第三个测试用例：
- 满足条件的最长子序列为 $s_1s_2s_4s_5s_6s_8 = ()(())$，因此答案为 $6$。