There are N players standing in a line, indexed 1 to N from left to right. They all play a game of Rock, Paper, Scissors. Each player has already decided which move they want to play. You are given this information as a string S of length N, i.e,

S_{i} is equal to $\verb+R+$ if player i will play Rock.
S_{i} is equal to $\verb+P+$ if player i will play Paper.
S_{i} is equal to $\verb+S+$ if player i will play Scissors.

Let W(i, j) denote the move played by the winner if players $i, i+1, \ldots, j$ compete in order from left to right. That is,
First, players i and i+1 play a game
The winner of this game plays against player i+2
The winner of the second game plays against player i+3

$\vdots$

The winner of the first j-i-1 games plays against player j, and the move played by the winner of this game is declared to be W(i, j).

If i = j, then player i is considered to be the winner and W(i, i) = S_{i}.

Your task is to find the value of W(i,N) for all i from 1 to N.

Note :
If a person with index i and index j (i < j) play against each other, then:
If $S_{i} \neq S_{j}$, the winner is decided by classical rules, i.e, rock beats scissors, scissors beats paper, and paper beats rock.
If S_{i} = S_{j}, the player with lower index (in this case, i) wins.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N, the number of players.
• The second line of each test case contains the string S of length N, denoting the moves chosen by the players.

------ Output Format ------

For each test case, print a single line containing a string of length N, whose i-th character is W(i, N).

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 5\cdot 10^{5}$
$S_{i}$ is either $\verb+R+$, $\verb+P+$ or $\verb+S+$
- Sum of $N$ over all test cases doesn't exceed $5 \cdot 10^{5}$

------ subtasks ------

Subtask 1 (10 points):
$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 5000$
Sum of $N$ over all test cases doesn't exceed $5000$

Subtask 2 (90 points):
Original constraints

----- Sample Input 1 ------
2
1
S
4
SSPR
----- Sample Output 1 ------
S
RRPR
----- explanation 1 ------

Test Case 1. $W(1,1) = \verb+S+$ as there is only one player.

Test Case 2.

For $W(1,4)$ the game is played as follows :
- Player $1$ and $2$ compete, player $1$ wins.
- Player $1$ and $3$ compete, player $1$ wins.
- Player $1$ and $4$ compete, player $4$ wins.

Hence, we print $W(1,4) = S_{4} = \verb+R+$

For $W(3,4)$ the game is played as follows :
- Player $3$ and $4$ compete, player $3$ wins.

Hence, we print $W(3,4) = S_{3} = \verb+P+$

见题面

见题面