秦谷美鈴のプロデューサーは、「曇りの日さえレッスンをすれば、ひとまずそれでよい」というとんでもない約束を担当アイドルと交わしてしまいました。それ以外のレッスンは勝手に休むことになるため、このままでは担当アイドルもろとも留年です。 （参考：学園アイドルマスター 秦谷美鈴親愛度コミュ第2話・一部脚色）
S 、 C からなる長さ \(N\) の文字列 \(S\) が与えられます。 \(S\) の \(i\) 文字目が S であることは今日から \(i\) 日後の天気がこのままだと晴れであることを表します。同様に、 C なら曇りです。 今日の天気は晴れであるため、担当アイドルは絶賛お昼寝中です。
あなたは、今日から毎晩曇り乞いをするかどうかを選ぶことができます。 曇り乞いをした場合、 \(1/2\) の確率で曇り乞いの効果が発揮され、次の日の天気が強制的に曇りになります。 ただし、担当アイドルの機嫌を損ねないようにするために、直前 \(3\) 日の天気がすべて曇りであった場合は曇り乞いをすることができません。 逆に、そうでない場合はその日の天気にかかわらず曇り乞いをすることとします。
今後 \(N\) 日のうち天気が曇りとなる日数の期待値を \(\mathrm{mod}\ 998244353\) で求めてください。つまり、求める期待値を既約分数 \(y/x\) で表したとき、
を満たす \(z\) が（本問題の制約において）一意に存在するので、その値を求めてください。
\(1\) 回の実行で複数のテストケース（ \(T\) 個）が与えられるので、すべて処理してください。
入力は以下の形式で標準入力から与えられます。
| \(T\) | |
| \(N_1\) | |
| \(S_1\) | |
| \(N_2\) | |
| \(S_2\) | |
| \(\vdots\) | |
| \(N_T\) | |
| \(S_T\) |
ただし、 \(N _ i\) , \(S _ i\) (\(i=1,2,\ldots ,T\)) は、 \(i\) 個目のテストケースにおける \(N\) , \(S\) を表します。
制約は以下の通りです。
各テストケースについて、答えを \(1\) 行に出力してください。
34CSCS5SCSCS10SSSCSCSCCS
249561091 748683268 467927047
サンプル \(1\) について:
天気が曇りとなる日数の期待値は、順に、 \(\dfrac{11}{4}\) , \(\dfrac{13}{4}\) , \(\dfrac{209}{32}\) です。