题目描述

Y 同学正在检查一些尚未写完的括号序列。一个合法括号序列长度为 $2N$，由 $N$ 个左括号和 $N$ 个右括号组成，并且从左到右读任意前缀时，左括号数量都不少于右括号数量。

现在给定一个已经写好的前缀 $S$，Y 同学想知道有多少种方式可以继续添加括号，使得最终得到一个长度为 $2N$ 的合法括号序列。如果前缀本身已经违反合法括号序列的前缀条件，或者左右括号数量不可能补足，则答案为 $0$。

请你回答多个这样的询问，输出每个答案对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $Q$。

接下来 $Q$ 行，每行先给出一个整数 $N$，再给出一个仅由 ( 与 ) 组成的字符串 $S$。

输出格式

对每个询问输出一行一个整数，表示补全方案数对 $998244353$ 取模后的结果。

样例

样例输入 #1

3
3 ((
3 ()
4 (()

样例输出 #1

3
2
5

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le Q\le 2\times 10^5$，$1\le N\le 10^6$，所有 $S$ 的长度之和不超过 $2\times 10^5$。

特殊性质 A：保证所有 $S$ 只包含左括号。

特殊性质 B：保证所有 $S$ 本身都是合法括号序列前缀。