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>

// template : secondThread

import java.io.*;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;



public   class main2 {





      public static void main(String[] args) {
          try {


              PrintWriter fop = new PrintWriter(System.out);
              FastScanner fsca = new FastScanner();

            int t = fsca.nextInt();
            while (t-- > 0){
                char A[] = fsca.next().toCharArray() ;
                int stone_ct = 0 , scissor_ct = 0 , paper_ct = 0 ;
                for (int i = 0; i <A.length ; i++) {
                    if (A[i] == 'R')
                        stone_ct++ ;
                    else if (A[i] == 'P')
                        paper_ct++ ;
                    else
                        scissor_ct++ ;
                }

                int max = Math.max(scissor_ct , Math.max(stone_ct , paper_ct)) ;

               StringBuilder sb = new StringBuilder() ;
                if (max == paper_ct){
                    for (int i = 0; i <A.length ; i++)
                    sb.append("S") ;
                }
                else if (max == stone_ct){
                    for (int i = 0; i <A.length ; i++)
                    sb.append("P") ;}
                else {
                    for (int i = 0; i <A.length ; i++)
                        sb.append("R") ;
                }
                fop.println(sb);

            }
























              fop.flush();
              fop.close();
          } catch (Exception e) {
              return;
          }


      }
      /*-----------------------------------------------------------------------------------------------------------------------------------------------*/


      static void sieve(int n) {
          boolean[] flag = new boolean[n];

          for (int i = 2; i * i < n; i++) {
              if (flag[i])
                  continue;
              else
                  for (int j = i * i; j <= n; j += i) {
                      flag[j] = true;
                  }
          }
      }


      static int gcd(int a, int b) {
          if (b > a) {
              int tenp = b;
              b = a;
              a = tenp;
          }
          int temp = 0;
          while (b != 0) {
              a %= b;
              temp = b;
              b = a;
              a = temp;
          }
          return a;
      }

      static long gcd_long(long a, long b) {
          if (b > a) {
              long tenp = b;
              b = a;
              a = tenp;
          }
          long temp = 0;
          while (b != 0) {
              a %= b;
              temp = b;
              b = a;
              a = temp;
          }
          return a;
      }


      static final Random random = new Random();

      static void ruffleSort(int[] a) {
          int n = a.length;//shuffle, then sort
          for (int i = 0; i < n; i++) {
              int oi = random.nextInt(n), temp = a[oi];
              a[oi] = a[i];
              a[i] = temp;
          }
          Arrays.sort(a);
      }


      static class FastScanner {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer("");

          String next() {
              while (!st.hasMoreTokens())
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              return st.nextToken();
          }

          int nextInt() {
              return Integer.parseInt(next());
          }

          int[] readArray(int n) {
              int[] a = new int[n];
              for (int i = 0; i < n; i++) a[i] = nextInt();
              return a;
          }

          long[] readLongArray(int n) {
              long[] a = new long[n];
              for (int i = 0; i < n; i++)
                  a[i] = nextLong();
              return a;
          }

          long nextLong() {
              return Long.parseLong(next());
          }
      }


  }








