题目描述

对于字符串 $S$，$T$，定义 $S$ 的字典序小于 $T$ 当且仅当以下三者之一成立：

• $S$ 为空串（长度为 $0$），$T$ 为非空串；
• $S,T$ 为非空串，且 $S[0]$ 字典序小于 $T[0]$，这里 $S[0],T[0]$ 表示 $S,T$ 的首个字符；
• $S,T$ 为非空串，且 $S[0]=T[0]$，$S[1,\cdots]$ 字典序小于 $T[1,\cdots]$，这里 $S[1,\cdots],T[1,\cdots]$ 表示 $S,T$ 删除首个字符得到的字符串。

对于由 $\texttt{\{`(',`)'\}}$ 组成的括号串 $S$，称其为可匹配的，当且仅当以下三者之一成立：

• $S$ 是空串（长度为 $0$）；
• $S = (A)$，其中 $A$ 是可匹配的括号串；
• $S = AB$，其中 $A$，$B$ 都是可匹配的非空括号串。

下面给出一个可匹配的括号串 $T$，求有多少个括号串 $S$ 满足以下四个条件：

• $S$ 不是空串（长度大于 $0$）；
• $S$ 是可匹配的；
• $S=T$，或 $S$ 的字典序小于 $T$；
• $S$ 的长度小于等于 $T$ 的长度。

注意，符号 $\texttt{`('}$ 的字典序比 $\texttt{`)'}$ 小。

本题采用多组测试。答案可能很大，请输出结果对 $998244353$ 取模后的余数。

输入格式

每个测试点第一行包含一个正整数 $t$（$1 \le t \le 5\times 10^5$），表示数据组数。

接下来 $t$ 组数据，每组数据第一行为一个偶数 $n$（$2\le n\le 10^6$），表示字符串 $T$ 的长度。

第二行为一个长度为 $n$ 的括号串，其字符集为 $\texttt{\{`(',`)'\}}$。这里保证 $T$ 是可匹配的。

保证单个测试点内所有括号串的长度总和不超过 $10^6$。

输出格式

输出 $t$ 行，第 $i$ 行表示第 $i$ 组数据的答案对 $998244353$ 取模后的余数。

6
2
()
4
()()
4
(())
6
()(())
8
(())(())
20
((()())(()())(()()))

1
3
1
6
11
7346

提示

对于第四组数据，有以下六个符合要求的 $S$：

• $\texttt{()}$
• $\texttt{(())}$
• $\texttt{()(())}$
• $\texttt{(())()}$
• $\texttt{((()))}$
• $\texttt{(()())}$