410617: GYM104065 M Rock-Paper-Scissors Pyramid

The rock-paper-scissors is a well-known hand game that originated in China, usually played between two people, in which each player simultaneously forms one of three shapes with an outstretched hand. These shapes are "rock" (a closed fist), "paper" (a flat hand), and "scissors" (a fist with the index finger and middle finger extended, forming a V). "Scissors" is identical to the two-fingered V sign (also indicating "victory" or "peace") except that it is pointed horizontally instead of being held upright in the air. The rule is simple. Paper beats rock. Rock beats scissors. Scissors beats paper.

Example of Rock Paper Scissors. Source: Wikipedia

We use the uppercase letters $$$\mathrm{R}$$$, $$$\textrm{P}$$$ and $$$\textrm{S}$$$ to represent rock, paper and scissors, respectively. Given an initial string $$$s$$$ containing $$$\mathrm{R}$$$, $$$\textrm{P}$$$ and $$$\textrm{S}$$$ of length $$$n$$$. Bobo designs a "rock-paper-scissors" pyramid of height and base length $$$n$$$ as follows: Place the initial string $$$s$$$ placed at the bottom $$$n$$$ blocks in order, then the pyramid evolves by the following rule:

• If the two blocks immediately below a block have the same shape (namely, both are $$$\mathrm{R}$$$, $$$\textrm{P}$$$, or $$$\textrm{S}$$$), we will place the same shape on the block.
• If the two blocks immediately below a block have different shapes, we will place the winning shape on the block.

Refer to the pictures in the notes section for a clearer illustration.

Bobo wants to know, following this rule, what is the shape at the top of the pyramid?

The first line contains an integer $$$T$$$, denoting the number of test cases.

For each test case, a string $$$s(1\leq |s|\leq 10^6)$$$ containing only symbols '$$$\mathrm{R}$$$', '$$$\mathrm{P}$$$' and '$$$\mathrm{S}$$$' is given as the configuration on the bottom of the pyramid.

It is the guaranteed that the sum of lengths over all strings doesn't exceed $$$10^6$$$.

For each test case, output a character $$$c\in \{$$$'$$$\mathrm{R}$$$', '$$$\mathrm{P}$$$', '$$$\mathrm{S}$$$'$$$\}$$$ in a line, denoting the shape at the top of the pyramid.

2
SPR
SPSRRP

S
P

The following picture gives an example with initial string $$$\mathrm{SPR}$$$, as in the first test case of the sample test.

The following picture gives an example with initial string $$$\mathrm{SPSRRP}$$$, as in the second test case of the sample test.