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 java.io.*;
import java.util.*;




public class CodeForce {
 static ArrayList<Integer> inputarrlist(String s){
     String[] str=s.split(" ");
     ArrayList<Integer> arr=new ArrayList<>();
     for(int i=0;i<str.length;i++)
         arr.add(Integer.parseInt(str[i]));
     
     return arr;
 }
 static long[] inputarrlong(String s){
     String[] str=s.split(" ");
     long[] arr=new long[str.length];
     for(int i=0;i<str.length;i++)
         arr[i]=(Long.parseLong(str[i]));
     
     return arr;
 }
 
 static int[] inputarrint(String s){
     String[] str=s.split(" ");
     int[] arr=new int[str.length];
     for(int i=0;i<str.length;i++)
         arr[i]=Integer.parseInt(str[i]);
     
     return arr;
 }
 
 static int powermod(long x, long y, long mod){
  long ans = 1;
  while(y>0){
      if (y%2==1)
           ans = (ans*x)%mod;
           x = (x*x)%mod;
	   y/=2;
            }
   return (int)(ans);
	}
 
 static int power(long x, long y){
  long ans = 1;
  while(y>0){
      if (y%2==1)
           ans=ans*x;
           x=(x*x);
	   y/=2;
            }
   return (int)(ans);
	}
 
 static StringBuffer rrotatestring(StringBuffer sb,int a){
     int len=sb.length();
     StringBuffer temp;
      temp=new StringBuffer(sb.substring(len-a, len));
      sb.delete(len-a,len);
      sb.insert(0,temp);
      return sb;
 }
 
 static StringBuffer lrotatestring(StringBuffer sb,int a){
     int len=sb.length();
     StringBuffer temp;
      temp=new StringBuffer(sb.substring(0,a));
      sb.delete(0,a);
      sb.append(temp);
      return sb;
 }
 static long gcd(long a, long b) 
    { 
      if (b==0) 
        return a; 
      return gcd(b, a % b);  
    } 
 
 static long lcm(long a,long b) 
    { 
        return (a*b)/gcd(a, b); 
    } 
 
 
 static ArrayList<Long> allfactorsofn(long n) 
    { 
        ArrayList<Long> a=new ArrayList<>();
        ArrayList<Long> b=new ArrayList<>();
        for (long i=1; i<=Math.sqrt(n); i++) 
        { if (n%i==0) 
            {  
                if (n/i == i) 
                    a.add(i); 
       
                else 
                {
                    a.add(i);
                    b.add(n/i);
                }
            } 
        } 
        
        for(int i=b.size()-1;i>=0;i--){
            a.add(b.get(i));
        }
        
        return a;
    } 
 
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        
        //t=1;

        t=Integer.parseInt(br.readLine());
        
        while(t-->0){
             char[] ch=br.readLine().toCharArray();
             StringBuffer sb=new StringBuffer();
            int s=0,r=0,p=0;
             for(int i=0;i<ch.length;i++){
                if(ch[i]=='R')
                    r++;
                else if(ch[i]=='P')
                    p++;
                else
                    s++;
            }
             char c;
             if(r>=Math.max(s, p))
                 c='P';
             else if(p>=Math.max(r,s))
                 c='S';
             else
                 c='R';
             for(int i=0;i<ch.length;i++)
                 sb.append(c);
            System.out.println(sb);
        }
    }

class Sample{
            int x;
            int y;
            Sample(int x, int y){
                this.x= x;
                this.y=y;
            }
        }
        class SortSample implements Comparator<Sample>{
            public int compare(Sample a ,Sample b){
                if(a.x!=b.x)
                return a.x-b.x;
                else
                    return a.y-b.y;
            }
        }
}