A16556 | Sub-RBS (Hard Version)

本题为该问题的困难版本。不同版本间的差异在于：本版本需要计算 $s$ 的**所有子序列**的得分之和；$s$ 不一定是正则括号序列；同时对 $n$ 的约束条件更宽松。

我们称括号序列 $a$ 比括号序列 $b$ **更优**，当且仅当满足以下任一条件：
1. $b$ 是 $a$ 的前缀，但 $a \ne b$；
2. 设 $i$ 是 $a$ 和 $b$ 第一个出现字符不同的位置（若存在），且满足 $a_i = \texttt{(}$ 且 $b_i = \texttt{)}$。

对于任意括号序列 $t$，其**得分**定义如下：
1. 若 $t$ 不是正则括号序列$^{∗}$，则得分为 $0$；
2. 若存在 $t$ 的一个正则括号子序列$^{†}$ $r$ 满足 $r$ 比 $t$ 更优，则得分为所有此类子序列 $r$ 的长度 $|r|$ 的最大值；
3. 否则，得分为 $0$。

换句话说，$t$ 的得分等于：$t$ 的所有“比 $t$ 更优”的正则括号子序列中，最长子序列的长度。若 $t$ 不是正则括号序列，或不存在比 $t$ 更优的正则子序列，则得分为 $0$。

给定一个长度为 $n$ 的括号序列 $s$，请计算 $s$ 的所有**非空**子序列的得分之和，并对 $998\,244\,353$ 取模。

$^{∗}$ 正则括号序列（Regular Bracket Sequence, RBS）的定义：将序列中原有字符间插入字符 $\texttt{1}$ 和 $\texttt{+}$ 后，能转化为合法算术表达式的括号序列。例如：
- 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正则的（转化后的表达式分别为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）；
- 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 不是正则的。

$^{†}$ 子序列的定义：若序列 $a$ 可通过删除序列 $b$ 中任意位置的若干个（可能为 0 个或全部）元素得到，则称 $a$ 是 $b$ 的子序列。

输入包含多组测试用例。第一行输入测试用例数 $t$（$1 \le t \le 30$），后续为各测试用例的描述。

每组测试用例的第一行输入一个整数 $n$（$1 \le n \le 100$），表示字符串 $s$ 的长度。
第二行输入一个长度为 $n$ 的字符串 $s$，仅由字符 $\texttt{(}$ 和 $\texttt{)}$ 组成。

保证所有测试用例的 $n$ 之和不超过 $100$。

对于每组测试用例，输出一个整数：$s$ 的所有非空子序列的得分之和，对 $998\,244\,353$ 取模后的结果。