有一个大正方形 $ABCD$（顶点按逆时针顺序排列）。在它的每个顶点上都有一个钉子。此外还有两根长绳，一根连接顶点 $A$ 和 $B$，另一根连接顶点 $C$ 和 $D$。每个钉子将绳子的一端固定在地面上。绳子可以无限伸缩，但它们永远不能离开正方形上方的区域。最初，绳子是未缠绕的：也就是说，如果将它们充分收缩，其中一根绳子会沿着正方形的一条边，而另一根绳子会沿着相对的边。

有一个名为 Ka-BAN 的机器人，它可以执行两条指令：

• spin，记作 $S$：将绳子的所有四个末端从钉子上取下，绕垂直轴逆时针旋转 $90^\circ$，保持绳子之间的所有缠绕状态，然后重新连接到新的钉子上。或者，也可以将此操作理解为正方形、钉子和绳子保持不动，但顶点的名称顺时针旋转 $90^\circ$：

  • 顶点 $A$ 的新名称为 $B$；
  • 顶点 $B$ 的新名称为 $C$；
  • 顶点 $C$ 的新名称为 $D$；
  • 顶点 $D$ 的新名称为 $A$； 对于本题而言，这两种操作是等价的。

• rotate，记作 $R$：Ka-BAN 将绳子从钉子 $A$ 和 $D$ 上取下，交换它们，然后重新连接回去。在交换过程中，最初连接在 $A$ 上的绳端会从最初连接在 $D$ 上的绳端上方穿过。如果站在正方形外靠近边 $AD$ 的位置观察这个过程，看起来就像端点 $A$ 和端点 $D$ 绕着彼此逆时针旋转了 $180^\circ$。

你有一个由字母 “S” 和 “R” 组成的字符串，这是 Ka-BAN 执行的程序：指令按从左到右的顺序依次执行。不幸的是，在这个过程之后，正方形和绳子看起来像是一团乱麻。为了解决这个问题，你买了一个新机器人 Iz-BAN。当你阅读手册时，你感到非常惊讶：Iz-BAN 拥有与 Ka-BAN 相同的两条指令！这意味着解开缠绕变得很困难：尽管任何 $S$ 操作都可以通过再执行三次 $S$ 操作来撤销，但似乎没有简单的方法来撤销 $R$ 操作。

然而，可以证明这两条操作足以解决这个问题！给定 Ka-BAN 执行的程序，请为 Iz-BAN 编写最短的程序，使得在执行该程序后，绳子再次变得未缠绕。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 300\,000$)。 接下来的 $T$ 行，每行包含一个由字母 “S” 和 “R” 组成的字符串 $s$：这是 Ka-BAN 执行的程序 ($1 \le |s| \le 300\,000$)。所有测试用例中字符串长度之和不超过 $300\,000$。

输出格式

对于每个测试用例，输出一行由字母 “S” 和 “R” 组成的字符串：可以给 Iz-BAN 执行以解开绳子的最短程序。如果绳子已经处于未缠绕状态，则输出一个字母 “S”。可以证明答案总是存在且唯一的。

样例

输入格式 1

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

输出格式 1

SR
S
SRSRR
S
R
S
SRSRRSRR
S
S
SR
RSRR
S
SR
S

输入格式 2

5
SRRSRRSRR
SRRRSRRR
RRRSRRRSRRR
SRRSRRSRRSRRSRRSRRSRRSRRSR
SRRRSRRRSRRRSRRRSRRRSRRRSRRRS

输出格式 2

SRSRR
SRSRRSRR
SRSRRSRRRSRRRSRR
SRRRRRRRRR
RSRRSRRRSRRRSRRRSRRRSRRRSRR