Statement

为了追上 Daniel13265，皮卡丘爬上了一棵神树……

这棵树可以看作是一棵二叉树，最开始有一个根节点，每过一秒，所有的叶子节点就会产生两个儿子，若一个点不足两个儿子，会自动补上另一个。

但这棵树被 Daniel13265 施了魔法：

1. 疯狂生长：时间快进 $T$ 秒。
2. 攻击：让皮卡丘再次再次回到初始节点，这时皮卡丘会产生一个包含 $L,R$ 的序列 $S$（保证不为空），表示从根节点向左儿子或右儿子移动，最终皮卡丘会停在某个节点（Daniel13265 保证皮卡丘不会走出这棵树），然后 Daniel13265 会炸掉这个节点（这个节点及其子树都将丢失）。

皮卡丘想知道每个操作完成后，树的节点有多少个。显然这个数会很大，你需要输出对 $998244353$ 取模的答案。

Task

input

第一行一个数 $t$，表示数据组数

对于每一组数据：

第一行一个数 $n$，表示操作次数

接下来 $n$ 行，是下面两种方式：

1. $G$ $T$ 表示时间快进 $T$ 秒
2. $A$ $S$ 表示皮卡丘从根节点开始按照 $S$ 的指示行走，并摧毁停下的节点

output

总共 $\sum n$ 行，每行表示树的节点对 $998244353$ 取模的答案

Sample I

input

2
6
G 1
A L
G 1
A R
G 1
G 1
3
G 3
A LR
A RRR

output

3
2
5
2
5
11
15
12
11

Constraints

对于全部数据满足 $1 \le t \le 10^5$ $t \le \sum n \le 10^6$ $1\le \sum|S|,\sum T \le 10^6$（这里的$\sum$代表所有数据）

前 $20\%$ 的数据满足：$1\le n,\sum|S|,\sum T \le 15$ ，$t\leq 10$（这里的$\sum$代表每一组数据）

另有 $10\%$ 的数据满足：只有第一种操作

另有 $10\%$ 的数据满足：每组数据内，任何一个 $S$ 都不会是另一个的前缀

另有 $30\%$ 的数据满足：$t \le \sum n \le 10^5$ $\sum|S|,\sum T\le 10^5$（这里的$\sum$代表所有数据）