题目描述

合法括号序列是只由 ( 和 ) 组成，并且可以通过插入若干个 $1$ 和 $+$ 变成合法数学表达式的序列。例如 ()(()()) 是合法括号序列，而 ())(() 和 (() 不是。

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

现在考虑把一个子序列向右循环移动。形式化地说，若选择的下标为 $i_1<i_2<\cdots<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_2S_4$ 会把 $S$ 变成 ((())())；移动子序列 $S_2S_3S_5$ 会把 $S$ 变成 ())((())。

请计算有多少个非空子序列在执行这种右移之后，仍能让 $S$ 保持为合法括号序列。答案对 $998244353$ 取模。

子序列可以通过删除原序列中若干个位置得到；若删除的位置集合不同，则认为子序列不同。

输入格式

第一行一个整数 $t$，表示测试组数。

每组数据第一行一个偶数 $n$。

第二行一个长度为 $n$ 的合法括号序列 $S$，字符串中不含空格。

输出格式

对每组数据输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例

4
2
()
4
()()
6
(()())
10
()((())())

2
8
28
312

说明

第二个样例中，有 $8$ 个非空子序列移动后仍保持合法括号序列，分别为 $S_1$、$S_2$、$S_3$、$S_4$、$S_1S_3$、$S_2S_3$、$S_2S_4$、$S_1S_2S_3$。

数据范围

$1\le t\le10^4$，$2\le n\le300000$，且 $n$ 为偶数。

所有测试组的 $n$ 之和不超过 $300000$。