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 ... 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 ≤ pos ≤ 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 ... c_n and if the bot starts from index pos then you'll win in win(pos) rounds. Find c_1 c_2 ... c_n such that (win(1) + win(2) + ... + win(n))/(n) is maximum possible.

Input

The first line contains a single integer t (1 ≤ t ≤ 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 ... s_{n} (1 ≤ n ≤ 2 ⋅ 10^5; s_i ∈ \{R, S, P\}) — the string of the bot.

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

Output

For each test case, print n choices c_1 c_2 ... 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 (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: 

<image>
"Codeforces Round #384 (Div. 2)"
"C. Vladik and fractions"
# y=int(input())
# a=y
# b=a+1
# c=y*b
# if y==1:
#     print(-1)
# else:    
#     print(a,b,c)
"Technocup 2017 - Elimination Round 2"
"D. Sea Battle"
# n,a,b,k=map(int,input().split())
# s=list(input())
# n=len(s)
# lz=[]
# zeros=[]
# indexes=[]
# flage=0
# if s[0]=="0":
#     lz.append(0)
#     flage=1  
# for i in range(1,n):
#     if flage==1 and s[i]=="1":
#         zeros.append(i-1-(lz[-1])+1)
#         lz.append(i-1)
#         flage=0
#     elif flage==0 and s[i]=="0":
#         lz.append(i)
#         flage=1   

# if s[-1]=="0":
#     zeros.append(n-1-(lz[-1])+1)
#     lz.append(n-1)
# min_no_spaces=(a-1)*b
# spaces_left=n-k    
# l=len(lz)    
# # print(lz)
# # print(zeros)  
# shot=0
# for i in range(len(zeros)):
#     h=i*2
#     if min_no_spaces!=0:
#         # print(min_no_spaces)
#         if min_no_spaces>=zeros[i]:
#             min_no_spaces-=(int(zeros[i]/b))*b
#         elif min_no_spaces<zeros[i]:
#             shot+=int((zeros[i]-min_no_spaces)/b)
#             for j in range(int((zeros[i]-min_no_spaces)/b)):
#                 indexes.append(lz[h]+((j+1)*b))
#             min_no_spaces=0    
#     elif min_no_spaces==0:
#         # print(min_no_spaces)
#         shot+=int(zeros[i]/b)
#         for j in range(int(zeros[i]/b)):
#             indexes.append(lz[h]+((j+1)*b))
# print(shot)
# for i in indexes:
#     print(i," ",end="",sep="")
"Codeforces Round #268 (Div. 1)"
"A. 24 Game"
# y=int(input())
# a=[u for u in range(1,y+1)]
# if y>5:
#     print("YES")
#     print("6 * 4 = 24")
#     print("5 - 3 = 2")
#     print("2 - 2 = 0")
#     print("1 * 0 = 0")
#     for i in range(7,y+1):
#         print(i,"* 0 = 0")
#     print("24 + 0 = 24")
# elif y==5:
#     print("YES")
#     print("5 + 1 = 6")
#     print("6 * 2 = 12")
#     print("4 * 3 = 12")
#     print("12 + 12 = 24")
# elif y==4:
#     print("YES")
#     print("1 * 2 = 2")
#     print("3 * 4 = 12")
#     print("2 * 12 = 24")
# else:
#     print("NO")  
"Educational Codeforces Round 91 (Rated for Div. 2)"
"B. Universal Solution"
y=int(input())
for i in range(y):
    r=input()
    s=""
    R=S=P=0
    for j in r:
        if j=="R":
            s+="P"
            R+=1
        elif j=="S":
            s+="R"
            S+=1
        else:
            s+="S"
            P+=1
    if P==R and S==R:
        print("R"*len(r))
    elif R>=S and R>=P:           
        print("P"*len(r))
    elif S>=R and S>=P:           
        print("R"*len(r))
    elif P>=S and P>=R:           
        print("S"*len(r))                                      