描述

猫猫$A$和猫猫$B$原本是关系很好的猫猫，但是突然有一天，两只猫猫都宣布以后所有活动再也不与对方排在一起(即位置上相邻)，一旦把他们放在一起的话就会跑掉。猫猫头很纳闷，想知道将所有猫猫排成一排或环形队伍后有多少种让猫猫$A$和猫猫$B$不逃跑的可能。

输入格式

给定样例数量 $T\ (1\le T\le10^5)$

对于每个样例，占一行，每行给出一个字符串$S\ (S\in\{Line,Cycle\})$一个正整数$n\ (1\le n \le 10^7)$ 按空格分隔。

输出格式

对于每个样例，输出给定 $n$ 个猫猫时（猫猫$A$和猫猫$B$总是到场的），输出有多少种猫猫$A$和猫猫$B$不逃跑的可能数，可能数会很大，请将结果对 $998244353$ 取模后输出。

样例

input

4
Line 3
Cycle 4
Cycle 5
Line 5

output

2
2
12
72

提示

对于第一个样例，第三个猫猫只能排中间，$A,B$排两边因此共有两种可能。

对于第二个样例，围起来看，保证不同位置上看能够完全不相同的，仅仅是第三第四的猫猫互相交换位置，也等价于$A,B$猫猫互相交换位置。因此也仅有两种可能。