题目描述

Yuki 发现一个回文括号串不可能是平衡括号串，因此她设计了另一种定义回文平衡括号串的方式。

Yuki 按照如下规则定义了 回文括号串：

• 空串是回文括号串。
• $\texttt($ 和 $\texttt)$ 是回文括号串。
• 若括号串 $s$ 是回文括号串，则 $\texttt( s \texttt($ 和 $\texttt) s \texttt)$ 是回文括号串。

Yuki 按照如下规则定义了 平衡括号串：

• 空串是平衡括号串。
• 若括号串 $s$ 是平衡括号串，则 $\texttt{(}s\texttt{)}$ 是平衡括号串。
• 若括号串 $s,t$ 均是平衡括号串，则 $st$（两括号串拼接起来）是平衡括号串。

对于一个括号串 $s = s_1 \dots s_n$，Yuki 定义 $s$ 是 回文平衡括号串，当且仅当：

• $s_2 \dots s_{n-1}$ 是回文括号串。
• $s_1 \dots s_n$ 是平衡括号串。

特殊地，空串和 $\texttt{()}$ 也为回文平衡括号串。

例如，$\texttt{(())()}$ 和 $\texttt{()()(()())}$ 是回文平衡括号串，而 $\texttt{((()))}$ 和 $\texttt{()()(())}$ 不是。

现在，Yuki 有一个长度为 $n$ 的括号串 $s$，她希望找到一个 $s$ 的最长的子序列$^\ast$，使得该子序列是回文平衡括号串。不过 Yuki 并不知道怎么做，因此你需要帮助她求出 $s$ 的最长的满足条件的子序列的长度。

$^\ast$：称序列 $a$ 是序列 $b$ 的子序列，当且仅当序列 $a$ 能够通过在序列 $b$ 的基础上删除任意个元素（可以为 $0$ 个）得到；特殊地，空序列是任何序列的子序列。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $t$ $(1 \le t \le 5000)$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个正整数 $n$ $(1 \le n \le 5000)$。
• 第二行包含一个长度为 $n$ 的括号串 $s$ $(s_i \in \{\texttt(,\texttt)\})$。

保证所有测试数据中 $n$ 的总和不超过 $10^4$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 $s$ 的最长的满足条件的子序列的长度。

3
5
(()((
7
)))((((
8
())(()()

2
0
6

提示

对于第 $1$ 组测试数据：

• 最长的满足条件的子序列为 $s_1s_3 = \texttt{()}$ 和 $s_2s_3 = \texttt{()}$，答案为 $2$。

对于第 $2$ 组测试数据：

• 最长的满足条件的子序列为空串，答案为 $0$。

对于第 $3$ 组测试数据：

• 最长的满足条件的子序列为 $s_1s_2s_4s_5s_6s_8 = \texttt{()(())}$，答案为 $6$。