Recently, you found a bot to play "Rock paper scissors" with. Unfortunately, the bot uses quite a simple algorithm to play: he has a string $s = s_1 s_2 \dots s_{n}$ of length $n$ where each letter is either R, S or P.

While initializing, the bot is choosing a starting index $pos$ ($1 \le pos \le n$), and then it can play any number of rounds. In the first round, he chooses "Rock", "Scissors" or "Paper" based on the value of $s_{pos}$:   if $s_{pos}$ is equal to R the bot chooses "Rock";  if $s_{pos}$ is equal to S the bot chooses "Scissors";  if $s_{pos}$ is equal to P the bot chooses "Paper"; 

In the second round, the bot's choice is based on the value of $s_{pos + 1}$. In the third round — on $s_{pos + 2}$ and so on. After $s_n$ the bot returns to $s_1$ and continues his game.

You plan to play $n$ rounds and you've already figured out the string $s$ but still don't know what is the starting index $pos$. But since the bot's tactic is so boring, you've decided to find $n$ choices to each round to maximize the average number of wins.

In other words, let's suggest your choices are $c_1 c_2 \dots c_n$ and if the bot starts from index $pos$ then you'll win in $win(pos)$ rounds. Find $c_1 c_2 \dots c_n$ such that $\frac{win(1) + win(2) + \dots + win(n)}{n}$ is maximum possible.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Next $t$ lines contain test cases — one per line. The first and only line of each test case contains string $s = s_1 s_2 \dots s_{n}$ ($1 \le n \le 2 \cdot 10^5$; $s_i \in \{\text{R}, \text{S}, \text{P}\}$) — the string of the bot.

It's guaranteed that the total length of all strings in one test doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print $n$ choices $c_1 c_2 \dots c_n$ to maximize the average number of wins. Print them in the same manner as the string $s$.

If there are multiple optimal answers, print any of them.


-----Example-----
Input
3
RRRR
RSP
S

Output
PPPP
RSP
R


-----Note-----

In the first test case, the bot (wherever it starts) will always choose "Rock", so we can always choose "Paper". So, in any case, we will win all $n = 4$ rounds, so the average is also equal to $4$.

In the second test case:   if bot will start from $pos = 1$, then $(s_1, c_1)$ is draw, $(s_2, c_2)$ is draw and $(s_3, c_3)$ is draw, so $win(1) = 0$;  if bot will start from $pos = 2$, then $(s_2, c_1)$ is win, $(s_3, c_2)$ is win and $(s_1, c_3)$ is win, so $win(2) = 3$;  if bot will start from $pos = 3$, then $(s_3, c_1)$ is lose, $(s_1, c_2)$ is lose and $(s_2, c_3)$ is lose, so $win(3) = 0$;  The average is equal to $\frac{0 + 3 + 0}{3} = 1$ and it can be proven that it's the maximum possible average.

A picture from Wikipedia explaining "Rock paper scissors" game:  $\beta$

Difficulty: interview

Starter code:

Solutions:
#
#    ------------------------------------------------
#           ____          _     Generatered using
#          / ___|        | |
#         | |    __ _  __| | ___ _ __  ______ _
#         | |   / _` |/ _` |/ _ \ '_ \|_  / _` |
#         | |__| (_| | (_| |  __/ | | |/ / (_| |
#          \____\____|\____|\___|_| |_/___\____|
#
#      GNU Affero General Public License v3.0
#    ------------------------------------------------
#    Author   : prophet
#    Created  : 2020-07-12 11:19:01.523119
#    UUID     : aXsU7xuXyjk3Ky2f
#    ------------------------------------------------
#
production = True

import sys, math, collections

def input(input_format = 0, multi = 0):

    if multi > 0: return [input(input_format) for i in range(multi)]
    else:
        next_line = sys.stdin.readline()[:-1]

        if input_format >= 10:
            use_list = False
            input_format = int(str(input_format)[-1])
        else: use_list = True

        if input_format == 0: formatted_input = [next_line]
        elif input_format == 1: formatted_input = list(map(int, next_line.split()))
        elif input_format == 2: formatted_input = list(map(float, next_line.split()))
        elif input_format == 3: formatted_input = list(next_line)
        elif input_format == 4: formatted_input = list(map(int, list(next_line)))
        elif input_format == 5: formatted_input = next_line.split()
        else: formatted_input = [next_line]

        return formatted_input if use_list else formatted_input[0]

def out(output_line, output_format = 0, newline = True):

    formatted_output = ""

    if output_format == 0: formatted_output = str(output_line)
    elif output_format == 1: formatted_output = " ".join(map(str, output_line))
    elif output_format == 2: formatted_output = "\n".join(map(str, output_line))

    print(formatted_output, end = "\n" if newline else "")

def log(*args):
    if not production:
        print("$$$", end = "")
        print(*args)

enu = enumerate

ter = lambda a, b, c: b if a else c

ceil = lambda a, b: -(-a // b)

def mapl(iterable, format = 0):
    
    if format == 0: return list(map(int, iterable))
    elif format == 1: return list(map(str, iterable))
    elif format == 2: return list(map(list, iterable))
#
#   >>>>>>>>>>>>>>> START OF SOLUTION <<<<<<<<<<<<<<
#


def solve():

    s = input(3)

    u = [0] * 3

    for i in s:
        if i == "R":
            u[0] += 1
        elif i == "P":
            u[1] += 1
        elif i == "S":
            u[2] += 1

    log(u)
    y = 0
    p = 0

    for i, j in enu(u):
        if j > y:
            y = j
            p = i

    if p == 0:
        a = "P"
    elif p == 1:
        a = "S"
    elif p == 2:
        a = "R"

    out(a * len(s))

    return


for i in range(input(11)): solve()
# solve()

#
#   >>>>>>>>>>>>>>>> END OF SOLUTION <<<<<<<<<<<<<<<
#


# import sys
from collections import Counter
# input = sys.stdin.readline

# T = int(input())

# for t in range(T):
#     s = input()
#     pos = set(range(len(s)))

#     answer = ['']

#     for i in range(len(s)):
#         lets = [s[k] for k in pos]
#         if not pos:
#             break
#         cc = Counter(lets)
#         fl = cc.most_common()[0][0]
#         choice = ''
#         if fl == 'R':
#             choice = 'P'
#         elif fl == 'S':
#             choice = 'R'
#         else:
#             choice = 'S'
#         answer.append(choice)
#         next_pos = set()
#         for p in pos:
#             if s[p] == choice:
#                 np = p+1
#                 if np >= len(s):
#                     np = 0
#                 next_pos.add(np)
#         pos = next_pos

#     while len(answer) < len(s):
#         answer.append('R')

#     print(''.join(answer))

T = int(input())

for t in range(T):
    s = input()
    cc = Counter(s)
    fl = cc.most_common()[0][0]
    if fl == 'R':
        choice = 'P'
    elif fl == 'S':
        choice = 'R'
    else:
        choice = 'S'
    print(choice*len(s))


T = int(input())
for _ in range(T):
    s = input().strip()
    rc = 0
    sc = 0
    pc = 0
    for c in s:
        if c == 'R':
            rc += 1
        elif c == 'S':
            sc += 1
        else:
            pc += 1
    if rc == max(rc,sc,pc):
        print('P'*len(s))
    elif sc == max(rc,sc,pc):
        print('R'*len(s))
    else:
        print('S'*len(s))



t=int(input())
for you in range(t):
    s=input()
    n=len(s)
    numofr=0
    numofs=0
    numofp=0
    for i in s:
        if(i=='R'):
            numofr+=1
        elif(i=='S'):
            numofs+=1
        else:
            numofp+=1
    z=max(numofr,numofp,numofs)
    if(z==numofr):
        print('P'*n)
    elif(z==numofs):
        print('R'*n)
    else:
        print('S'*n)

import sys
import math
import collections
import heapq

def set_debug(debug_mode=False):
    if debug_mode:
        fin = open('input.txt', 'r')
        sys.stdin = fin


def int_input():
    return list(map(int, input().split()))


def __starting_point():
    # set_debug(True)

    t = int(input())
    # t = 1

    for ti in range(1, t + 1):
        # n = int(input())
        s = input()

        c = collections.Counter(s)
        m = max(c['R'], c['S'], c['P'])

        if m == c['R']:
            print('P' * len(s))
        elif m == c['S']:
            print('R' * len(s))
        else:
            print('S' * len(s))

__starting_point()

t = int(input())
for _ in range(t):
    s = input()
    n = len(s)
    cnt_r = s.count("R")
    cnt_s = s.count("S")
    cnt_p = s.count("P")
    max_cnt = max(cnt_r, cnt_s, cnt_p)

    if max_cnt == cnt_r:
        print("P" * n)
    elif max_cnt == cnt_s:
        print("R" * n)
    else:
        print("S" * n)

for _ in range(int(input())):
	s = input()
	d = dict()
	d['R'] = 0
	d['S'] = 0
	d['P'] = 0
	d1 = dict()
	d1['R'] = 'P'
	d1['S'] = 'R'
	d1['P'] = 'S'
	for i in s:
		d[i] += 1
	ans = ''
	c = ''
	mx = -1
	for i in list(d.items()):
		if mx < i[1]:
			c = d1[i[0]]
			mx = i[1]
	print(c * len(s))


import sys

t = int(sys.stdin.readline().strip())
for _ in range(t):
	s = sys.stdin.readline().strip()
	x, y, z = s.count('R'), s.count('S'), s.count('P')
	if max(x, y, z) == x:
		print('P'*len(s))
	elif max(x, y, z) == y:
		print('R'*len(s))
	else:
		print('S'*len(s))

#!/usr/bin/env python3

from collections import Counter

def ans(S):
	freqs = Counter(S)
	arg_max = max(freqs, key=freqs.get)
	d = {
		'R': 'P',
		'P': 'S',
		'S': 'R'
	}
	return d[arg_max]*len(S)

T = int(input())
for t in range(T):
	S = input()
	print(ans(S))


t=int(input())
for _ in range(t):
  s=input()
  rcount=0
  pcount=0
  scount=0
  for i in range(len(s)):
    if s[i]=='R':
      rcount+=1
    if s[i]=='S':
      scount+=1
    if s[i]=='P':
      pcount+=1
  ans=[]
  if rcount>=pcount and rcount>=scount:
    for i in range(len(s)):
      ans.append('P')
  elif scount>=pcount and scount>=rcount:
    for i in range(len(s)):
      ans.append('R')
  else:
    for i in range(len(s)):
      ans.append('S')
  print(''.join(ans))

import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
	s = SI()
	ans = ""
	d = {"R":"P","S":"R","P":"S"}
	m = 0
	if s.count("R")>m:
		m = s.count("R")
		ans = "R"
	if s.count("S")>m:
		m = s.count("S")
		ans = "S"
	if s.count("P")>m:
		ans = "P"
	ans = d[ans]
	print(ans*len(s))