小红的gcd

题号：NC307613
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红定义一个长为 $3\times k$ 的好串为：由连续的 $k$ 个 $\texttt{g}$ ， $k$ 个 $\texttt{c}$ 和 $k$ 个 $\texttt{d}$ 拼接而成的字符串。
$\hspace{15pt}$ 例如一个长为 $6$ 的好串可以是 $\texttt{ggccdd}$ ，也可以是 $\texttt{ccddgg}$ ；而 $\texttt{gcgcdd}$ 不是一个好串。
$\hspace{15pt}$ 现在小红拿到了一个 $n \times n$ （保证 $2\times n - 1$ 是 $3$ 的倍数。）的仅包含 $\texttt{g,c,d}$ 的字符矩阵，她初始位于左上角，每次移动仅可以向下或向右移动一位。
$\hspace{15pt}$ 小红想知道，从矩阵左上角走到右下角的所有路径中，途径的所有字符依次拼接而成的字符串是一个好串的路径有多少个，请你帮帮她。由于结果可能很大，请将答案对 $998244353$ 取模后输出。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 。
之后的  行，每行输入  个字符，构成一个  的字符矩阵。
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行。
输出一个整数，代表符合条件的路径数量对  取模后的值。

示例1

输入

复制

2
2
gc
cd
5
cccgg
gggdg
ddggd
gggcd
ddddd

输出

复制

2
3