This is the hard version of the problem. The difference between the versions is that in this version, you need to find the sum of scores over all subsequences of $$$s$$$; $$$s$$$ is not necessarily a regular bracket sequence, and the constraints on $$$n$$$ are lower.

We say that a bracket sequence $$$a$$$ is better than a bracket sequence $$$b$$$ if one of the following holds:

$$$b$$$ is a prefix of $$$a$$$, but $$$a \ne b$$$; or
let $$$i$$$ be the first position (if it exists) where $$$a_i \neq b_i$$$, then $$$\color{red}{a_i = \texttt{(}}$$$ and $$$\color{red}{b_i = \texttt{)}}$$$.

For an arbitrary bracket sequence $$$t$$$, we define its score in the following way:

If $$$t$$$ is not a regular bracket sequence$$$^{\text{∗}}$$$, the score is $$$0$$$.
If there exists a regular bracket subsequence $$$^{\text{†}}$$$ $$$r$$$ of $$$t$$$ such that $$$r$$$ is better than $$$t$$$, then the score is equal to the maximum value of $$$|r|$$$ over all such subsequences $$$r$$$.
Otherwise, the score is $$$0$$$.

In other words, the score of $$$t$$$ is the length of the longest regular bracket subsequence of $$$t$$$ which is better than $$$t$$$. If $$$t$$$ is not a regular bracket sequence, or if no regular subsequence better than $$$t$$$ exists, the score is $$$0$$$.

You are given a bracket sequence $$$s$$$ of length $$$n$$$. Find the sum of the scores of all non-empty subsequences of $$$s$$$ modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $$$\texttt{1}$$$ and $$$\texttt{+}$$$ between the original characters of the sequence. For example:

bracket sequences $$$\texttt{()()}$$$ and $$$\texttt{(())}$$$ are regular (the resulting expressions are $$$\texttt{(1)+(1)}$$$ and $$$\texttt{((1+1)+1)}$$$);
bracket sequences $$$\texttt{)(}$$$, $$$\texttt{(}$$$, and $$$\texttt{)}$$$ are not.

$$$^{\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.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the string $$$s$$$.

The second line of each test case contains a sequence $$$s$$$ of length $$$n$$$ consisting only of characters $$$\texttt{(}$$$ and $$$\texttt{)}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100$$$.

Output

For each test case, print a single integer — the sum of the scores of all subsequences of $$$s$$$, modulo $$$998\,244\,353$$$.

Note

In the first example, the only non-empty subsequence is $$$g = \texttt{(}$$$. It is not a regular bracket sequence, so its score is $$$0$$$, and the total sum is also $$$0$$$.

In the second example, consider $$$g = s = \texttt{()()()}$$$. It is a regular bracket sequence. We can choose $$$r = \texttt{(())}$$$, which is a subsequence of $$$g$$$. The first index where $$$r$$$ and $$$g$$$ differ is $$$i = 2$$$. Since $$$r_2 = \texttt{(}$$$ and $$$g_2 = \texttt{)}$$$, $$$r$$$ is better than $$$g$$$. Hence, the score of $$$g$$$ is $$$|r| = 4$$$. All the other non-empty subsequences of $$$s$$$ have scores equal to $$$0$$$.

✓	#	Name		✎	Rating↕	Solved↕
	2190B2	Sub-RBS (Hard Version) dp games implementation strings			1900	3.4k
	455B	A Lot of Games dfs and similar dp games implementation strings trees			1900	7.1k

Problemset