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