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>
//  package com.company;
 import java.math.BigInteger;
 import java.util.*;
 import java.io.*;
 import java.lang.*;

 public class Main{

     public static void main(String args[]){
         PrintWriter out=new PrintWriter(System.out);
         InputReader in=new InputReader(System.in);
         TASK solver = new TASK();
         int t = in.nextInt();
//        int t=1;
         /*
          ** @author Jigar_Nainuji
          ** SVNIT-SURAT
          */
         for(int i=0;i<t;i++)
         {
             solver.solve(in,out,i);
         }
         out.close();
     }
     static class TASK {
         static int mod = 998244353;
         void solve(InputReader in, PrintWriter out, int testNumber) {
          char[] ch = in.next().toCharArray();
          int r=0,s=0,p=0;
          for(int i=0;i<ch.length;i++)
          {
              if(ch[i]=='P')
                  p++;
              if(ch[i]=='R')
                  r++;
              if(ch[i]=='S')
                  s++;
          }
          if(r>=s && r>=p)
          {
              for(int i=0;i<ch.length;i++)
                  System.out.print("P");
              System.out.println();
          }
          else if(p>=s && r<=p)
          {
              for(int i=0;i<ch.length;i++)
                  System.out.print("S");
              System.out.println();
          }
          else if(r<=s && s>=p)
          {
              for(int i=0;i<ch.length;i++)
                  System.out.print("R");
              System.out.println();
          }


         }
     }

     static class pair{
         int x;
         int y;
         pair(int x,int y)
         {
             this.x=x;
             this.y=y;
         }

     }
     static class Maths{
         static int gcd(int a, int b) {
             if (a == 0)
                 return b;
             return gcd(b % a, a);
         }



         public static long factorial(int n){
             long fact = 1;
             for(int i=1;i<=n;i++){
                 fact *= i;
             }
             return fact;
         }
     }


     static class InputReader {
         private InputStream stream;
         private byte[] buf = new byte[1024];
         private int curChar;
         private int numChars;
         private SpaceCharFilter filter;

         public InputReader(InputStream stream) {
             this.stream = stream;
         }

         public int read() {
             if (numChars == -1)
                 throw new InputMismatchException();

             if (curChar >= numChars) {
                 curChar = 0;
                 try {
                     numChars = stream.read(buf);
                 } catch (IOException e) {
                     throw new InputMismatchException();
                 }

                 if (numChars <= 0)
                     return -1;
             }
             return buf[curChar++];
         }

         public String nextLine() {
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             String str = "";
             try {
                 str = br.readLine();
             } catch (IOException e) {
                 e.printStackTrace();
             }
             return str;
         }

         public int nextInt() {
             int c = read();

             while (isSpaceChar(c))
                 c = read();

             int sgn = 1;

             if (c == '-') {
                 sgn = -1;
                 c = read();
             }

             int res = 0;
             do {
                 if (c < '0' || c > '9')
                     throw new InputMismatchException();
                 res *= 10;
                 res += c - '0';
                 c = read();
             }
             while (!isSpaceChar(c));

             return res * sgn;
         }

         public long nextLong() {
             int c = read();
             while (isSpaceChar(c))
                 c = read();
             int sgn = 1;
             if (c == '-') {
                 sgn = -1;
                 c = read();
             }
             long res = 0;

             do {
                 if (c < '0' || c > '9')
                     throw new InputMismatchException();
                 res *= 10;
                 res += c - '0';
                 c = read();
             }
             while (!isSpaceChar(c));
             return res * sgn;
         }

         public double nextDouble() {
             int c = read();
             while (isSpaceChar(c))
                 c = read();
             int sgn = 1;
             if (c == '-') {
                 sgn = -1;
                 c = read();
             }
             double res = 0;
             while (!isSpaceChar(c) && c != '.') {
                 if (c == 'e' || c == 'E')
                     return res * Math.pow(10, nextInt());
                 if (c < '0' || c > '9')
                     throw new InputMismatchException();
                 res *= 10;
                 res += c - '0';
                 c = read();
             }
             if (c == '.') {
                 c = read();
                 double m = 1;
                 while (!isSpaceChar(c)) {
                     if (c == 'e' || c == 'E')
                         return res * Math.pow(10, nextInt());
                     if (c < '0' || c > '9')
                         throw new InputMismatchException();
                     m /= 10;
                     res += (c - '0') * m;
                     c = read();
                 }
             }
             return res * sgn;
         }

         public String readString() {
             int c = read();
             while (isSpaceChar(c))
                 c = read();
             StringBuilder res = new StringBuilder();
             do {
                 res.appendCodePoint(c);
                 c = read();
             }
             while (!isSpaceChar(c));

             return res.toString();
         }

         public boolean isSpaceChar(int c) {
             if (filter != null)
                 return filter.isSpaceChar(c);
             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
         }

         public String next() {
             return readString();
         }

         public interface SpaceCharFilter {
             public boolean isSpaceChar(int ch);
         }
     }
 }
