AT_abc464_g [ABC464G] Celester 2

これから $ N $ 日間の天気が文字列 $ S $ として与えられます。 $ S $ の $ i $ 文字目が `S` であるとき $ i $ 日目の天気は晴れ、 `R` であるとき $ i $ 日目の天気は雨です。 あなたは、以下の操作を $ 0 $ 回以上 $ k $ 回まで行うことができます。 - $ 1 $ 以上 $ N $ 以下の整数 $ i $ を選択する。 - $ i $ 日目の天気が晴れであれば雨、雨であれば晴れに変更する。 操作を行った後の最終的な天気に対して、以下の条件で嬉しさを得ます。 - $ 1 \le i \le N-1 $ を満たす各整数 $ i $ について、変更後の $ i $ 日目の天気が雨、かつ $ i+1 $ 日目の天気が晴れであるとき、嬉しさを $ 1 $ 得る。 各 $ k=0,1,\dots,N $ について、操作を高々 $ k $ 回行った時に得る嬉しさの合計の最大値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{case}_i $ は $ i $ 個目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ S $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 個目のテストケースの答えを出力せよ。 各テストケースについて、 $ k=i $ とした場合の答えを $ A_i $ とする。このとき、以下の形式で答えを出力せよ。 > $ A_0 $ $ A_1 $ $ \dots $ $ A_N $

### Sample Explanation 1 この入力には $ 5 $ 個のテストケースが含まれています。 $ 1 $ 個目のテストケースについて: - 操作前の各日の天気は順に 晴れ、晴れ、晴れ、雨です。 - $ k=0 $ である場合、操作は行えません。 - 操作後の各日の天気は 晴れ、晴れ、晴れ、雨 となり、得る嬉しさの合計は $ 0 $ であり、これが達成可能な最大です。 - $ k=1 $ である場合、例えば $ 2 $ 日目の天気を変更することが最適です。 - 操作後の各日の天気は 晴れ、雨、晴れ、雨 となり、得る嬉しさの合計は $ 1 $ であり、これが達成可能な最大です。 - $ k=2 $ である場合、例えば $ 1,2 $ 日目の天気を変更することが最適です。 - 操作後の各日の天気は 雨、雨、晴れ、雨 となり、得る嬉しさの合計は $ 1 $ であり、これが達成可能な最大です。 - $ k=3 $ である場合、例えば $ 1,3,4 $ 日目の天気を変更することが最適です。 - 操作後の各日の天気は 雨、晴れ、雨、晴れ となり、得る嬉しさの合計は $ 2 $ であり、これが達成可能な最大です。 - $ k=4 $ である場合、例えば $ 1,3,4 $ 日目の天気を変更することが最適です。 - 操作後の各日の天気は 雨、晴れ、雨、晴れ となり、得る嬉しさの合計は $ 2 $ であり、これが達成可能な最大です。 ### Constraints - $ 1 \le T \le 10^4 $ - $ N $ は $ 2 $ 以上 $ 10^6 $ 以下の整数 - $ S $ は長さ $ N $ の `S` と `R` からなる文字列 - ひとつの入力における $ N $ の総和は $ 10^6 $ 以下