题目描述

在一条水平线上有 $n$ 个人排成一队，每个人都向左或向右看。每个人都计算他们所看方向的人数。该队列的得分是每个人看到的人数的总和。

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

给你排队人员的初始朝向，对于从 $1$ 到 $n$ 的每个 $k$，请计算如果最多可以改变 $k$ 个人的方向，该队列的最大得分值。

输入格式

输入由多个测试用例组成。第一行包含整数 $t(1≤t≤100)$ 代表测试用例数。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n(1≤n≤2⋅10^5)$ 代表队列的长度。

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

保证所有测试用例的 $n$ 之和不超过 $2⋅10^5$。

某些测试用例的答案会超过 $32$ 位整数类型，因此您应该在编程语言中至少使用 $64$ 位整数类型。

输出格式

对于每个测试用例，输出 $n$ 个由空格分隔的非负整数，依次代表如果您可以改变 $1$ 到 $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$。注意，你最多改变 $k$ 个人的方向，但不必须。

在第二个测试用例中，对于所有 $k$，最好只将第一个人的方向从 L 更改为 R（即，使队列变为 RRRLL）。