时空限制

1S/512M

题目描述

给定两个字符串 $S_1$ 和 $S_2$，定义斐波那契字符串：对于 $i\geq 3$，第 $i$ 个字符串由在第 $i-2$ 个字符串后面连接上第 $i-1$ 个字符串得到，即 $S_i=S_{i-2}+S_{i-1}$。

比如 $S_1=$ w，$S_2=$ wo，那么 $S_3=S_1+S_2=$ w $+$ wo $=$ wwo， $S_4=S_2+S_3=$ wo $+$ wwo $=$ wowwo，以此类推。

字符串中如果连续三个字符依次为 w、o、w，算作出现了一个 wow。

给定字符串 $S_1$ 和 $S_2$，求 $S_n$ 中出现了多少个 wow，对 $998244353$ 取模。

共有 $T$ 组数据。

格式

输入格式

第一行包含一个整数 $T$，表示数据的组数。

对于每组数据：

第一行包含一个整数 $n$ 和两个仅由 w 和 o 这两种字符组成的字符串 $S_1,S_2$，含义与题目描述相同。

输出格式

对于每组数据，在单独的一行中输出一个整数，表示 $S_n$ 中出现了多少个 wow，对 $998244353$ 取模。

样例

样例输入 #1

5
20 woowwo wowo
54321 owow owwow
100000 woow w
100000 woow o
1000000000000000000 w o

样例输出 #1

10945
128310683
0
882432781
120975022

数据规模

对于 $20\%$ 的数据，$n\leq 15$。

对于 $60\%$ 的数据，$n\leq 10^5$。

对于 $100\%$ 的数据，$1\leq T\leq 100$，$3\leq n\leq 10^{18}$。数据保证 $S_1,S_2$ 的长度都不超过 $10$，保证 $S_1,S_2$ 仅由 w 和 o 这两种字符构成。