B. 括号序列
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

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

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

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

注意，符号 '(' 的字典序比 ')' 小。

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

Input

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

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

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

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

Output

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

Example
Input
6
2
()
4
()()
4
(())
6
()(())
8
(())(())
20
((()())(()())(()()))
Output
1
3
1
6
11
7346
Note

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

  • ()
  • (())
  • ()(())
  • (())()
  • ((()))
  • (()())