Problem Description

For strings $S$ and $T$, define that $S$ is lexicographically smaller than $T$ if and only if one of the following holds:

• $S$ is the empty string (length $0$), and $T$ is non-empty;
• $S$ and $T$ are non-empty, and $S[0]$ is lexicographically smaller than $T[0]$, where $S[0]$ and $T[0]$ denote the first character of $S$ and $T$;
• $S$ and $T$ are non-empty, and $S[0]=T[0]$, and $S[1,\cdots]$ is lexicographically smaller than $T[1,\cdots]$, where $S[1,\cdots]$ and $T[1,\cdots]$ denote the strings obtained by deleting the first character from $S$ and $T$.

For a bracket string $S$ consisting of $\texttt{\{`(',`)'\}}$, call it matchable if and only if one of the following holds:

• $S$ is the empty string (length $0$);
• $S = (A)$, where $A$ is a matchable bracket string;
• $S = AB$, where both $A$ and $B$ are non-empty matchable bracket strings.

Now a matchable bracket string $T$ is given. Find how many bracket strings $S$ satisfy all of the following four conditions:

• $S$ is not the empty string (length $> 0$);
• $S$ is matchable;
• $S=T$, or $S$ is lexicographically smaller than $T$;
• The length of $S$ is less than or equal to the length of $T$.

Note that the character $\texttt{`('}$ is lexicographically smaller than $\texttt{`)'}$.

This problem uses multiple test cases. The answer may be very large, so output the result modulo $998244353$.

Input Format

The first line of each test file contains a positive integer $t$ ($1 \le t \le 5\times 10^5$), the number of test cases.

Then follow $t$ test cases. For each test case, the first line contains an even integer $n$ ($2\le n\le 10^6$), the length of the string $T$.

The second line contains a bracket string of length $n$ over $\texttt{\{`(',`)'\}}$. It is guaranteed that $T$ is matchable.

It is guaranteed that the sum of lengths of all bracket strings in a single test file does not exceed $10^6$.

Output Format

Output $t$ lines. The $i$-th line should contain the answer for the $i$-th test case modulo $998244353$.

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

1
3
1
6
11
7346

Hint

For the fourth test case, there are the following six valid strings $S$:

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

Translated by ChatGPT 5