题目内容

在一行上有 $L$ 个位置，从左到右依次编号为 $1$ 到 $L$。每个位置上写有一个方向标记，标记仅为 'L'（表示向左）或 'R'（表示向右）。

一个弹珠从某个起始位置 $s$（$1 \le s \le L$）放下，随后按照以下规则反复移动：

1. 记当前位置为 $p$。若 $p$ 处的标记为 'L'，则弹珠向左移动；若为 'R'，则向右移动。
2. 沿该方向持续移动，直到首次遇到一个从前未曾停留过的位置，然后停下，并按该位置的标记开始下一轮移动。移动过程中经过的其他位置不改变运动方向。
3. 重复直到弹珠离开全部位置的范围。若从位置 $0$ 离开，记最终方向为 'L'；若从位置 $L+1$ 离开，记最终方向为 'R'。

现在给出若干个这样的标记序列，请你对每个序列，求出从每一个起始位置 $s = 1, 2, \dots, L$ 出发时，弹珠最终的离开方向，并输出一个长度为 $L$ 的字符串，其中第 $i$ 个字符即起始位置 $i$ 对应的方向。

约束

• 测试用例数目 $q$ 满足 $1 \le q \le 2 \times 10^5$。
• 每个序列的长度 $L$ 满足 $1 \le L \le 2 \times 10^5$，且所有序列的 $L$ 总和不超过 $2 \times 10^5$。
• 序列仅由字符 'L' 和 'R' 构成。

输入描述

第一行包含一个整数 $q$，表示用例个数。 接下来每两行为一组用例：

• 第一行为一个整数 $L$，表示序列的长度。
• 第二行为一个长度为 $L$ 的字符串，由字符 'L' 和 'R' 组成。 数据保证所有用例的 $L$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组用例，输出一行长度为 $L$ 的字符串，由 'L' 和 'R' 组成，其中第 $i$ 个字符表示从位置 $i$ 出发时弹珠的最终离开方向。

样例1

输入

1
1
R

输出

R

说明

序列长度为 1，仅包含一个 'R'。统计 L 的数量 $cnt=0$，因此从唯一的起点 1 出发，弹珠最终从右侧离开，输出一个 'R'。

样例2

输入

2
4
RLLR
5
RRRRL

输出

LLRR
LRRRR

说明

第一组长度为 4，字符串 "RLLR" 中 L 的数量 $cnt=2$，前 $cnt$ 个位置输出 'L'，后 $L-cnt$ 个位置输出 'R'，得到 "LLRR"。 第二组长度为 5，字符串 "RRRRL" 中 L 的数量 $cnt=1$，因此答案为 "LRRRR"。

样例3

输入

3
3
LLL
3
RRR
6
LRLRLR

输出

LLL
RRR
LLLRRR

说明

第一组全为 'L'，$cnt=3$，输出 "LLL"，即所有起点均从左侧离开。 第二组全为 'R'，$cnt=0$，输出 "RRR"，即所有起点均从右侧离开。 第三组 "LRLRLR" 中 'L' 与 'R' 交替出现，$cnt=3$，输出前 3 个位置为 'L'、后 3 个位置为 'R' 的字符串 "LLLRRR"。