CF2201C.Rigged Bracket Sequence

A regular bracket sequence is a sequence consisting of '(' and ')', which can be turned into a valid math expression by inserting $1$ and $+$ any number of times into the sequence. For example, the sequence "()(()())" is a regular bracket sequence, while "())(()" or "(()" are not regular bracket sequences.

You are given a regular bracket sequence $S$.

Let us consider shifting a subsequence$^{\text{∗}}$ to the right. Formally, when a subsequence $S_{i_1} S_{i_2} \ldots S_{i_k}$ is shifted to the right, the characters on the chosen indices simultaneously get reassigned as follows:

• $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}}$.

In other words, the element of the $j$-th chosen index gets reassigned to the $((j-2) \bmod k + 1)$-th chosen character.

For example, when $S$ is "()(()())", shifting the subsequence $S_2 S_4$ changes $S$ to "((())())". On the other hand, shifting $S_2 S_3 S_5$ changes $S$ to "())((())".

Please count how many non-empty subsequences make $S$ remain regular when shifted to the right. As the answer may be huge, you are only asked to output the answer modulo $998\,244\,353$.

$^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions. Two subsequences are considered different if the sets of positions of the deleted elements are different.

合法括号序列是指仅由字符 '(' 和 ')' 构成的序列，且可在其中任意位置插入若干个 1 和 + 后，使其成为一个合法的数学表达式。例如，序列 "()(()())" 是一个合法括号序列，而 ")(()" 或 "((" 则不是合法括号序列。

你被给定一个合法括号序列 $S$。

我们考虑将某个子序列$^{\text{∗}}$ 向右循环移位。形式化地，当子序列 $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$ 取模的结果。

$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的一个子序列，当且仅当 $a$ 可通过从 $b$ 中删除若干（可能为零个或全部）任意位置的元素得到。若两个子序列所删除的位置集合不同，则认为它们是不同的子序列。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 300\,000$, $n$ is even).

The second line of each test case contains a regular bracket sequence $S$ of length $n$ given as a string without spaces.

It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 300\,000$，且 $n$ 为偶数）。

每个测试用例的第二行包含一个长度为 $n$ 的合法括号序列 $S$，以无空格字符串形式给出。

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

For each test case, output the answer modulo $998\,244\,353$ on a separate line.

对于每个测试用例，在单独一行中输出答案对 $998\,244\,353$ 取模的结果。

For the second test case, the $8$ non-empty subsequences that make $S$ remain regular when shifted to the right are as follows:

• $S_1$: changes $S$ to "()()";
• $S_2$: changes $S$ to "()()";
• $S_3$: changes $S$ to "()()";
• $S_4$: changes $S$ to "()()";
• $S_1 S_3$: changes $S$ to "()()";
• $S_2 S_3$: changes $S$ to "(())";
• $S_2 S_4$: changes $S$ to "()()";
• $S_1 S_2 S_3$: changes $S$ to "(())".

对于第二个测试用例，使得 $S$ 在右移后仍保持合法的 $8$ 个非空子序列如下：

• $S_1$：将 $S$ 变为 "()()";
• $S_2$：将 $S$ 变为 "()()";
• $S_3$：将 $S$ 变为 "()()";
• $S_4$：将 $S$ 变为 "()()";
• $S_1 S_3$：将 $S$ 变为 "()()";
• $S_2 S_3$：将 $S$ 变为 "(())";
• $S_2 S_4$：将 $S$ 变为 "()()";
• $S_1 S_2 S_3$：将 $S$ 变为 "(())"。