题目描述

众所周知，观者一共有四种姿态。这次她玩腻了，决定将自己的姿态改为石头、剪刀、布三种姿态。

接下来的 $n$ 个时刻，她记录下自己每个时刻的状态得到了状态序列 $a_1,a_2,\cdots,a_n$。她想不断进行以下操作直到序列长度为一：

• 生成一个长度为 $n-1$ 的序列 $b_1,b_2,\cdots,b_{n-1}$，其中 $b_i=f(a_i,a_{i+1})$，$f$ 表示两个姿态按照“石头剪刀布”规则的胜者，平局默认前者胜利；
• 令 $a\leftarrow b,n\leftarrow n-1$，也就是说，将 $a$ 赋值为 $b$，将 $n$ 的值减一。

观者想知道，最后剩下的那个姿态是什么，多组询问。

提示：

我们记 R 表示石头，S 表示剪刀，P 表示布，那么有：

$$f(\text{R},\text{R})=\text{R},f(\text{R},\text{S})=\text{R},f(\text{R},\text{P})=\text{P}\\ f(\text{S},\text{R})=\text{R},f(\text{S},\text{S})=\text{S},f(\text{S},\text{P})=\text{S}\\ f(\text{P},\text{R})=\text{P},f(\text{P},\text{S})=\text{S},f(\text{P},\text{P})=\text{P}$$

输入格式

第一行一个正整数 $T$，表示询问组数。

接下来 $T$ 组数据，每组数据占一行，输入一个由 RSP 三个大写字母组成的字符串表示状态序列（R 表示石头，S 表示剪刀，P 表示布），$n$ 为序列的长度。

输出格式

$T$ 行每行一个字母，表示答案。

7
SS
RS
SSR
RSP
PPPS
PSRPPR
RSRPSS

S
R
R
R
S
P
S

样例 2~5 见下发文件：样例下载。

数据范围

对于 $100\%$ 的数据，$2\leqslant n\leqslant 10^6,\sum n\leqslant 2\times 10^6$，即所有数据的 $n$ 之和不超过 $2\times 10^6$。

特殊性质 A：保证任意连续三个字母不同。

特殊性质 B：保证相邻且不同的字母数量不超过 $1000$。

特殊性质 C：保证 $T\leqslant 5$。