AT_bogosortcontest_div1_i tatesoto decomposition

英小文字からなる文字列 $ X $ が与えられます。 以下を満たす空でない文字列の組 $ (A, E, O, S, T) $ の個数を $ 998244353 $ で割った余りを求めてください。 - $ X = T + A + T + E + S + O + T + O $ ここで、 $ + $ は文字列の結合を表します。 $ Q $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_Q $ 各テストケースは以下の形式で与えられる。 > $ X $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 - $ (A, E, O, S, T) = ( $ `a` $ , $ `e` $ , $ `o` $ , $ `s` $ , $ `t` $ ) $ が条件を満たします。 $ 2 $ つ目のテストケースについて、条件を満たす空でない文字列の組 $ (A, E, O, S, T) $ は存在しません。 $ 3 $ つ目のテストケースについて、 - $ (A, E, O, S, T) = ( $ `aa` $ , $ `e` $ , $ `oo` $ , $ `ess` $ , $ `tt` $ ) $ - $ (A, E, O, S, T) = ( $ `aa` $ , $ `ee` $ , $ `oo` $ , $ `ss` $ , $ `tt` $ ) $ - $ (A, E, O, S, T) = ( $ `aa` $ , $ `ees` $ , $ `oo` $ , $ `s` $ , $ `tt` $ ) $ の $ 3 $ つが条件を満たします。 ### Constraints - $ 1 \leq Q \leq 5 \times 10^4 $ - $ X $ は英小文字からなる文字列 - $ 8 \leq |X| \leq 4 \times 10^5 $ - すべてのテストケースにおける $ |X| $ の総和は $ 4 \times 10^5 $ 以下 - 入力される数値はすべて整数