Problem Statement

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.

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$.

Input

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

Output

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