题目描述

Alice 和 Bob 在玩剪刀石头布的游戏。游戏总共进行了 $n$ 轮，每一轮他们俩都会选取 $S$(剪刀)，$R$(石头)，$P$(布) 中的一个

• 如果两人的选择相同，则这一局是平局；
• 如果一人选择 $S$(剪刀)，一人选择 $P$(布)，则选择 $S$(剪刀) 的人获胜
• 如果一人选择 $R$(石头)，一人选择 $S$(剪刀)，则选择 $R$(石头) 的人获胜
• 如果一人选择 $P$(布)，一人选择 $R$(石头)，则选择 $P$(布) 的人获胜

现在给你一个长度为 $n$ 的字符串 s，代表 Alice 每轮的选择，请你帮助 Bob 做出每轮的选择，使得 Bob 获胜的轮数超过 $\lfloor n / 2 \rfloor$

如果 Bob 可以有多种方案，请输出字典序最小的方案

输入格式

第一行是数据的组数 $T$，接下来 $T$ 组数据

每组数据包含 $2$ 行，第一行是 $n$，代表轮数

第二行是一个只包含 $S, R, P$ 的长度为 $n$ 的字符串，代表 Alice 每轮的选择

输出格式

输出一个长度为 $n$ 的字符串，代表 Bob 每轮的选择

3
1
R
2
PS
3
RSP

P
SR
PPS

提示

【样例解释】

• 第三组样例中 Alice 的选择是 石头(R)， 剪刀(S)，布(P)
• Bob 可以选择 P(布)，R(石头)，S(剪刀)，能赢 3 轮
• 也可以选择 P(布)，P(布)，S(剪刀)，能赢 2 轮
• 但是 PPS 的字典序小于 PRS
• 所以最后输出 PPS

数据规模与限制

• $1 \le n \le 10^5$
• 1s, 1024KiB for each test case.

来源