该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 人排在一条水平线上，每个人都向左或向右看。每个人都数自己所看方向的人数。这个队伍的凝聚力就是每个人的计数之和。

例如，在 $LRRLL$ 排列的队伍中，$L$ 代表向左看的人，$R$ 代表向右看的人，每个人的计数为 $[0, 3, 2, 3, 4]$ ，值为 $0+3+2+3+4=12$ 。

给你的是队伍中最初的安排。对于从 $1$ 到 $n$ 的每个 $k$，如果最多可以改变 $k$ 人的方向，请确定这个队伍的最大凝聚力。

输入格式

第一行一个整数 $T$ （$1\le T \le 100$），代表 $T$ 组测试样例。

每个测试用例的第一行包含一个整数 $n$ （$1\le n \le 2\times10^5$） ，表示队伍人数。

接下来的一行包含一个由 $n$ 个字符组成的字符串，每个字符都是 $L$ 或 $R$，分别代表向左或向右的人。

保证所有测试用例中 $\sum n \le 2 \times 10^5$。

输出格式

输出 $T$ 行，每一行输出 $n$ 个整数代表满足的最大凝聚力。

输入样例

6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL

输出样例

3 5 5 
16 16 16 16 16 
0 
86 95 98 101 102 102 102 102 102 102 102 102 
29 38 45 52 57 62 65 68 69 70 
44 50 54 56 56 56 56 56 56 

提示

在第一个测试案例中

$k=1$ ：改变 $1$ 人的方向，使队伍成为 $RLR$。总值为 $2+1+0=3$ 。 $k=2$ ：改变 $2$ 人的方向，使队伍成为 $RLL$。总值为 $2+1+2=5$ 。 $k=3$ ：改变 $2$ 人的方向，使队伍成为 $RLL$。总值为 $2+1+2=5$ 。

在第二个测试案例中，从 $1$ 到 $5$ 的所有 $k$ 中，只改变第一个人的方向是最优的(即使队伍为 $RRRLL$)。