题目描述

33DAI 在安排一场比赛的出题进度。第 $1$ 天他出了 $1$ 道题。从第 $2$ 天到第 $n$ 天，每一天的情况由一个字符给出，字符 A、B、C 的含义分别是：

• A：这一天的出题数 = 前一天的出题数 $\times 2$；
• B：这一天的出题数 = 前一天的出题数 $\times 3$；
• C：这一天的出题数 = 前一天的出题数的算术平方根，即前一天的出题数是完全平方数时，取它的平方根。

请算出第 $n$ 天 33DAI 出了多少道题。因为这个数可能非常大，你只需要输出它除以 $998244353$ 的余数。

输入格式

输入的第一行是一个整数 $t$，表示测试用例组数。

接下来依次给出 $t$ 组测试用例，每组测试用例的格式为：

• 第一行一个整数 $n$，表示一共有多少天；
• 第二行一个长度为 $n-1$ 的字符串 $s$，其中 $s_i$ 表示第 $i+1$ 天的情况，$s_i \in \{\texttt{A}, \texttt{B}, \texttt{C}\}$。

特别地，当 $n = 1$ 时第二行是空行。

输出格式

对每组测试用例输出一行一个整数，表示该组第 $n$ 天的出题数除以 $998244353$ 的余数。

3
1

5
AABB
6
AABBC

1
36
6

样例 1 解释

第 1 组：$n = 1$，只有第一天，出了 $1$ 道题，$1$ 除以 $998244353$ 的余数是 $1$，输出 1。

第 2 组：字符串是 AABB，一共 $5$ 天，逐天算下去：

天	情况	出题数
1	—	1
2	A	$1 \times 2 = 2$
3		$2 \times 2 = 4$
4	B	$4 \times 3 = 12$
5		$12 \times 3 = 36$

所以第 $5$ 天出了 $36$ 道题，$36$ 除以 $998244353$ 的余数是 $36$，输出 36。

第 3 组：字符串是 AABBC，前 $5$ 天与第 2 组一样，第 $5$ 天出了 $36$ 道题。第 $6$ 天是 C，而 $36$ 是完全平方数，出题数取它的平方根，即 $6$ 道，输出 6。

1
43
AABBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBB

360597229

样例 2 解释

按题意逐天算下去，第 $43$ 天的出题数是 $112717121716224$。把它除以 $998244353$：

$$112717121716224 = 998244353 \times 112915 + 360597229$$

余数是 $360597229$，所以输出 360597229。

样例 3

见 grow3.in 与 grow3.ans。

样例 4

见 grow4.in 与 grow4.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 1000$；
• $1 \le n \le 10^5$；
• 字符串只由 A、B、C 组成，且长度为 $n-1$；
• C 只出现在前一天的出题数确实是完全平方数的时候；
• 所有测试用例的 $n$ 之和不超过 $10^5$。

子任务

本题共 20 个测试点，按测试点计分：

测试点	分值	每个测试点	特殊限制
$1 \sim 6$	$30$	$5$	$n \le 20$
$7 \sim 12$			$n \le 2000$
$13 \sim 20$	$40$		无额外限制

每个测试点单独评分，全部测试点的得分之和即为本题得分。