P17296 [ICPC 2026 Xi'an I] Palindromic and Balanced

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$ 的最长的满足条件的子序列的长度。

对于第 $1$ 组测试数据： - 最长的满足条件的子序列为 $s_1s_3 = \texttt{()}$ 和 $s_2s_3 = \texttt{()}$，答案为 $2$。 对于第 $2$ 组测试数据： - 最长的满足条件的子序列为空串，答案为 $0$。 对于第 $3$ 组测试数据： - 最长的满足条件的子序列为 $s_1s_2s_4s_5s_6s_8 = \texttt{()(())}$，答案为 $6$。