A16856 | Rigged Bracket Sequence

一个“正规括号序列”是仅由 “(” 和 “)” 组成的序列，可以通过在该序列中随意插入 $1$ 和 $+$ 变成合法的数学表达式。例如，序列“()(()())”是一个正规括号序列，而“())(()”或“(()”都不是正规括号序列。

现在给你一个正规括号序列 $S$。

我们定义右移一个子序列。具体地，若将子序列 $S_{i_1} S_{i_2} \ldots S_{i_k}$ 右移，则这些被选中位置上的字符会被同时重新赋值如下：

- $S_{i_1} \leftarrow S_{i_k}$；
- $S_{i_2} \leftarrow S_{i_1}$；
- $S_{i_3} \leftarrow S_{i_2}$；
- $\ldots$
- $S_{i_k} \leftarrow S_{i_{k-1}}$。

换句话说，第 $j$ 个被选中的位置被赋值为第 $((j-2) \bmod k + 1)$ 个被选中的字符。

例如，对于 $S$ 为 “()(()())”，若右移子序列 $S_2 S_4$，$S$ 会变为 “((())())”；若右移 $S_2 S_3 S_5$，则 $S$ 会变为 “())((())”。

请你统计，有多少个非空子序列，在右移后会使 $S$ 仍然保持为一个正规括号序列。由于答案可能非常大，只需输出答案对 $998\,244\,353$ 取模的结果。

$^{\ast}$ 序列 $a$ 是序列 $b$ 的子序列，若 $a$ 可以通过从 $b$ 中删除任意（可能为 0 个或全部）若干个元素后得到。如果所删除元素的位置不同，则认为是不同的子序列。

每组测试数据包含多组用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。
每组用例第一行为一个正偶整数 $n$（$2 \le n \le 300\,000$）。
第二行为一个长度为 $n$ 的正规括号序列 $S$，作为一个没有空格的字符串。

保证所有测试用例的 $n$ 之和不超过 $300\,000$。

对于每组测试用例，输出一个答案，每个答案占一行，对 $998\,244\,353$ 取模。