#P18127. Spin & Rotate!

Spin & Rotate!

Spin & Rotate!

有一个大正方形 ABCDABCD,顶点按逆时针顺序给出。每个顶点处都有一根固定绳索的钉子。有两条很长的绳子:一条连接顶点 A,BA,B,另一条连接顶点 C,DC,D。绳子的长度可以任意伸缩,但不能离开正方形上方的区域。

初始时两条绳子没有缠绕:如果把两条绳子都缩短,那么其中一条可以落在正方形的一条边上,另一条落在相对边上。

机器人 Ka-BAN 有两种操作:

  • S(spin):把四个绳端从钉子上取下,保持绳子之间的全部缠绕关系,绕竖直轴逆时针旋转 90∘90^\circ,再固定到新的钉子上。

    这等价于正方形和绳子不动,而把顶点名称顺时针旋转:

    • AA 的新名称是 BB;
    • BB 的新名称是 CC;
    • CC 的新名称是 DD;
    • DD 的新名称是 AA。
  • R(rotate):从顶点 A,DA,D 上取下绳端并交换后再固定。交换时,原来固定在 AA 的绳端从原来固定在 DD 的绳端上方越过。若从边 ADAD 外侧观察,相当于两个绳端绕彼此逆时针旋转 180∘180^\circ。

给定 Ka-BAN 从左到右执行的一串 S、R 操作。你需要为拥有同样两种操作的机器人 Iz-BAN 编写一个最短程序,使执行后两条绳子重新变得没有缠绕。

可以证明答案一定存在且唯一。如果绳子已经无缠绕,输出单个字符 S。

输入格式

第一行包含测试用例数 TT,满足 1≤T≤3000001\le T\le300000。

接下来 TT 行,每行包含一个只由 S、R 组成、长度为 ∣s∣|s| 的字符串,表示 Ka-BAN 执行的程序,满足

1≤∣s∣≤300000.1\le |s|\le300000.

所有字符串长度之和不超过 300000300000。

输出格式

对于每组数据,输出一行只含 S、R 的最短解缠程序。

样例 1

14
R
S
RR
SR
RS
SS
RRR
SRR
RSR
SSR
RRS
SRS
RSS
SSS
SR
S
SRSRR
S
R
S
SRSRRSRR
S
S
SR
RSRR
S
SR
S

样例 2

5
SRRSRRSRR
SRRRSRRR
RRRSRRRSRRR
SRRSRRSRRSRRSRRSRRSRRSRRSRRSR
SRRRSRRRSRRRSRRRSRRRSRRRSRRRS
SRSRRR
SRSRRSRR
SRSRRSRRRSRRRSRR
SRRRRRRRRR
RSRRSRRRSRRRSRRRSRRRSRRRSRR