B2. Sub-RBS (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Example
Input
5
1
(
6
()()()
6
(())()
8
(())()()
22
()()())()()(()()()((()
Output
0
4
0
22
563070
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$$$.