AT_abc464_g.Celester 2

The weather for the upcoming $N$ days is given as a string $S$.
If the $i$-th character of $S$ is S, then the weather on day $i$ is sunny; if it is R, then the weather on day $i$ is rainy.

You can perform the following operation between $0$ and $k$ times, inclusive:

• Choose an integer $i$ with $1 \le i \le N$.
• If the weather on day $i$ is sunny, change it to rainy; if it is rainy, change it to sunny.

After performing the operations, you gain happiness based on the final weather according to the following condition:

• For each integer $i$ with $1 \le i \le N-1$, if the weather on day $i$ after modification is rainy and the weather on day $i+1$ is sunny, your happiness increases by $1$.

For each $k = 0, 1, \dots, N$, find the maximum total happiness you can gain by performing the operation at most $k$ times.

$T$ test cases are given; solve each.

接下来 $N$ 天的天气情况由字符串 $S$ 给出。
若 $S$ 的第 $i$ 个字符为 S，则第 $i$ 天天气为晴天；若为 R，则第 $i$ 天天气为雨天。

你最多可执行以下操作 $k$ 次（包括执行 $0$ 次）：

• 选择一个整数 $i$，满足 $1 \le i \le N$；
• 若第 $i$ 天天气为晴天，则将其改为雨天；若为雨天，则改为晴天。

执行完若干次操作后，你的幸福值根据最终天气按如下规则计算：

• 对每个满足 $1 \le i \le N-1$ 的整数 $i$，若第 $i$ 天修改后的天气为雨天且第 $i+1$ 天天气为晴天，则幸福值增加 $1$。

对每个 $k = 0, 1, \dots, N$，求出在最多执行 $k$ 次操作的前提下所能获得的最大总幸福值。

共给出 $T$ 组测试数据，请分别求解。

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$
$S$

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$N$
$S$

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

For each test case, let $A_i$ be the answer for $k = i$. Then, output the answer in the following format:

$A_0$ $A_1$ $\dots$ $A_N$

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

对于每个测试用例，令 $A_i$ 表示 $k = i$ 时的答案。然后，按以下格式输出答案：

$A_0$ $A_1$ $\dots$ $A_N$

Sample 1 Explanation:
This input contains five test cases.

For the $1$st test case:

• The weather on each day before any operations is sunny, sunny, sunny, rainy in order.
• For $k = 0$, no operations can be performed.
  • The weather on each day after operations is sunny, sunny, sunny, rainy, and the total happiness is $0$, which is the achievable maximum.
• For $k = 1$, for example, changing the weather on day $2$ is optimal.
  • The weather on each day after operations is sunny, rainy, sunny, rainy, and the total happiness is $1$, which is the achievable maximum.
• For $k = 2$, for example, changing the weather on days $1$ and $2$ is optimal.
  • The weather on each day after operations is rainy, rainy, sunny, rainy, and the total happiness is $1$, which is the achievable maximum.
• For $k = 3$, for example, changing the weather on days $1$, $3$, and $4$ is optimal.
  • The weather on each day after operations is rainy, sunny, rainy, sunny, and the total happiness is $2$, which is the achievable maximum.
• For $k = 4$, for example, changing the weather on days $1$, $3$, and $4$ is optimal.
  • The weather on each day after operations is rainy, sunny, rainy, sunny, and the total happiness is $2$, which is the achievable maximum.

Constraints

• $1 \le T \le 10^4$
• $N$ is an integer between $2$ and $10^6$, inclusive.
• $S$ is a string of length $N$ consisting of S and R.
• The sum of $N$ in a single input is at most $10^6$.

样例 1 解释：
该输入包含五个测试用例。

对于第 $1$ 个测试用例：

• 在执行任何操作前，每天的天气依次为：晴、晴、晴、雨。
• 当 $k = 0$ 时，无法执行任何操作。
  • 操作后每天的天气仍为：晴、晴、晴、雨，总幸福感为 $0$，这是可达到的最大值。
• 当 $k = 1$ 时，例如将第 $2$ 天的天气改为雨是最优策略。
  • 操作后每天的天气为：晴、雨、晴、雨，总幸福感为 $1$，这是可达到的最大值。
• 当 $k = 2$ 时，例如将第 $1$ 天和第 $2$ 天的天气均改为雨是最优策略。
  • 操作后每天的天气为：雨、雨、晴、雨，总幸福感为 $1$，这是可达到的最大值。
• 当 $k = 3$ 时，例如将第 $1$、$3$、$4$ 天的天气分别改为雨、雨、晴（即：第 $1$ 天晴→雨，第 $3$ 天晴→雨，第 $4$ 天雨→晴）是最优策略。
  • 操作后每天的天气为：雨、晴、雨、晴，总幸福感为 $2$，这是可达到的最大值。
• 当 $k = 4$ 时，例如将第 $1$、$3$、$4$ 天的天气更改（同上），并额外更改一天（如第 $2$ 天晴→雨，但不影响结果）是最优策略。
  • 操作后每天的天气为：雨、晴、雨、晴，总幸福感为 $2$，这是可达到的最大值。

约束条件

• $1 \le T \le 10^4$
• $N$ 是介于 $2$ 和 $10^6$（含）之间的整数。
• $S$ 是一个长度为 $N$ 的字符串，仅由字符 S 和 R 组成。
• 单组输入中所有测试用例的 $N$ 之和不超过 $10^6$。