给定一个长度为 $2n$ 的字符串 $s$，其中包含 $n$ 个字符 W 和 $n$ 个字符 B。

让我们构建一个包含 $2n$ 个节点的图。如果对于某些 $1 \le i < j \le 2n$ 满足 $s_i \neq s_j$，则在节点 $i$ 和 $j$ 之间存在一条权重为 $|i - j|$ 的边。图中没有其他边。

求该图中长度最短的哈密顿回路的数量。由于该数字可能非常大，请输出其对 $998244353$ 取模的结果。

提醒一下，哈密顿回路是指访问每个节点恰好一次的回路。回路的长度等于其所有边的权重之和。如果两个回路包含的边集不同，则称它们为不同的回路。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 10^6$)。

每个测试用例的第二行包含一个长度为 $2n$ 的字符串 $s$，其中包含 $n$ 个字符 W 和 $n$ 个字符 B。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出该图中长度最短的哈密顿回路的数量，对 $998244353$ 取模。

样例

输入 1

3
2
WWBB
3
WBWBWB
7
WWWWBWBBWWBBBB

输出 1

1
2
62208

说明

在第一个测试用例中，该图有 4 条边：权重为 2 的 $(1, 3)$，权重为 3 的 $(1, 4)$，权重为 1 的 $(2, 3)$，以及权重为 2 的 $(2, 4)$。

这里存在唯一的哈密顿回路：$1 \to 3 \to 2 \to 4 \to 1$（注意，例如回路 $1 \to 4 \to 2 \to 3 \to 1$ 包含相同的边集，因此我们已经计算过它了）。