从标准输入读入数据。

我们使用一个长度为5的字符串来表示一个状态，其中，L表示面朝右的青蛙，R表示面朝左的青蛙，_（下划线）表示空格子。例如，初始状态为LL_RR。

本题含有多组数据，第一行两个整数T,C($1\le C\le 100$)分别表示测试点编号和数据组数。

对于每组数据，第一行一个整数n($1\le n\le 23$)表示不同状态的棋盘个数，接下来n行每行一个长度为5的字符串sis_is​i​​和一个正整数aia_ia​i​​(1≤ai≤1061\leq a_i\leq 10^61≤a​i​​≤10​6​​)，分别表示棋盘的状态和在该状态下的棋盘的个数。

保证输入的字符串合法且不重复。

输出到标准输出。

定义m=∑aim=\sum a_im=∑a​i​​。

对于每组数据，输出一行四个整数，分别表示小d必胜（即L的控制方必胜）、小m必胜（即R的控制方必胜）、先手必胜、后手必胜的概率乘2m2^m2​m​​之后对$998244353$取模的结果。

样例输入1

0 1
1
LL_RR 1

样例输出1

0 0 1 1

样例输入2

0 1
3
LRRL_ 1
LRR_L 1
LLR_R 1

样例输出2

4 2 0 2

样例输入3

0 1
1
LRRL_ 1000000

样例输出3

421273116 0 0 1

样例1解释

对于样例1，若该游戏没有被kill，双方唯一可能的操作序列为LL_RR -> L_LRR -> LRL_R -> LR_LR -> LRRL_ -> LRR_L -> L胜，小m先手时同理，故该情况为先手必胜。若该游戏被kill了，双方都没有合法行动，后手必胜。

样例2解释

对于样例2，令这三个棋盘的状态从上到下为A,B,C，则$\{A,B,C\},\{A,B\},\{A,C\},\{A\}$为小d必胜，$\{C\},\{B,C\}$为小m必胜，$\{B\},\{\}$为后手必胜。

保证数据中不会出现从LL_RR状态无法到达的状态（如RLLR_），故合法的状态共有23种。

定义 $k-$不可达点 为从LL_RR操作$k$次（双方加起来一共操作$k$次，顺序任意）后依然无法到达的合法状态，如 1-不可达点 为 ：全集$\setminus${LL_RR,L_LRR,LLR_R} 共20个， 5-不可达点 为{RLR_L,RRL_L,RR_LL,R_LRL,R_RLL}。

对于100%的数据，$1\le n\le 23$,1≤m≤1061\leq m\leq 10^61≤m≤10​6​​,$1\le C\le 100$，所有可能出现在该数据点的状态均为等概率出现（也就是说你可以认为最后一个点中每种状态的aia_ia​i​​之和大约为108/2310^8/2310​8​​/23）。