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>
import sys, os, io
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math,datetime,functools,itertools
from collections import deque,defaultdict,OrderedDict
import collections


def main():
    starttime=datetime.datetime.now()
    if(os.path.exists('input.txt')):
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    

    
    #Solving Area Starts-->

    #Solving Area Starts-->
    for _ in range(ri()):
        s=rs()
        ns,nr,np=0,0,0
        for i in s:
            if i=='R':
                nr+=1
            if i=='S':
                ns+=1
            if i=='P':
                np+=1
        
        z=[ns,nr,np]
        c=max(z)
        for i in z:
            if i==ns and i==c:
                print('R'*len(s))
                break
            if i==np and i==c:
                print('S'*len(s))
                break
            if i==nr and i==c:
                print('P'*len(s))
                break
            
            
            
        
                
                
                

        

                    
                
            

        
        
            
            
            
                
                
            
                
                
        

                
        
        

        
            
                
                
            
        
            
            
                
                

    

            
        
        
       
                
                    
                
            
            
        

            
            
                
            
            
        
                
        
                
                
            
        
            
                
                
                    
                
                
        
        


        
        
        
        

            
                    
            
                    
        
 

                
        
        

            
        
        
                
            
                
     
        
        
                
                
        
        
        
        
                
        

            
                
            


        
                
            
            
            
            
                    
        















    #<--Solving Area Ends
    endtime=datetime.datetime.now()
    time=(endtime-starttime).total_seconds()*1000
    if(os.path.exists('input.txt')):
        print("Time:",time,"ms")  
    
                
class FastReader(io.IOBase):
    newlines = 0

    def __init__(self, fd, chunk_size=1024 * 8):
        self._fd = fd
        self._chunk_size = chunk_size
        self.buffer = io.BytesIO()

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, size=-1):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()


class FastWriter(io.IOBase):

    def __init__(self, fd):
        self._fd = fd
        self.buffer = io.BytesIO()
        self.write = self.buffer.write

    def flush(self):
        os.write(self._fd, self.buffer.getvalue())
        self.buffer.truncate(0), self.buffer.seek(0)


class FastStdin(io.IOBase):
    def __init__(self, fd=0):
        self.buffer = FastReader(fd)
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


class FastStdout(io.IOBase):
    def __init__(self, fd=1):
        self.buffer = FastWriter(fd)
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.flush = self.buffer.flush


if __name__ == '__main__':
    sys.stdin = FastStdin()
    sys.stdout = FastStdout()
    main()







