H. 简单的 RBS 问题
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的合法括号串$$$^\dagger$$$ $$$S$$$，现在可以进行任意次以下操作（包含零次）：

  • 选择一个区间 $$$[l,r]$$$，且满足子串$$$^\ddagger$$$ $$$S[l\dots r]$$$ 是 RBS。
  • 翻转该区间。即将 $$$s_ls_{l+1}\dots s_{r-1}s_{r}$$$ 变成 $$$s_r,s_{r-1}\dots s_{l+1}s_l$$$。
  • 将该区间原本的 ( 变成 )，) 变成 (。

例如：()(()) 选择区间 $$$[1,6]$$$ 操作后变成 (())()，(()(())) 选择区间 $$$[2,7]$$$ 操作后变成 ((())())。

求操作任意次括号串后，一共有多少种可能的合法括号串结果，这个答案可能很大，你需要输出答案对 $$$998244353$$$ 取模后的结果。

$$$\dagger$$$ 合法括号串（RBS）：我们定义以下字符串为 RBS。

  • 空字符串是一个 RBS；
  • 如果 $$$S$$$ 是一个 RBS，那么 $$$(S)$$$ 也是一个 RBS；
  • 如果 $$$S$$$ 和 $$$T$$$ 都是 RBS，那么 $$$ST$$$（即 $$$S$$$ 和 $$$T$$$ 拼接）也是一个 RBS。
例如：
  • ()() 是 RBS。
  • (()()) 是 RBS。
  • )(()() 不是 RBS。

$$$\ddagger$$$ 子串：字符串 $$$S$$$ 的一个子串是由 $$$S$$$ 中连续的一段字符组成的序列。具体地，对于字符串 $$$S = s_1s_2\dots s_n$$$，其子串 $$$S[i \dots j]$$$ ($$$1 \le i \le j \le n$$$) 定义为字符串 $$$s_i s_{i+1} \dots s_j$$$。

Input

第一行输入一个正整数 $$$T(1\le T\le 10^4)$$$，表示测试数据组数。

接下来的 $$$T$$$ 组测试，对于每组测试，输入格式如下：

  • 第一行输入一个正整数 $$$n(2\le n\le 10^5)$$$，且保证 $$$n$$$ 为偶数。
  • 第二行输入一个长度为 $$$n$$$ 的合法括号序列（RBS） $$$S$$$。

此外，数据保证所有测试 $$$n$$$ 的总和不超过 $$$10^5$$$。

Output

对于每组数据，输出一个整数表示答案。

Example
Input
6
6
(()())
12
()(()(()))()
12
(()())(()())
12
(()())((()))
18
()(()(()))(()(()))
20
(())(())()(()((())))
Output
1
6
1
2
12
24