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.*;

import javax.lang.model.util.ElementScanner6;

public class B
{
    public static void main(String [] args) throws Exception
    {
        Foster sc = new Foster();
        PrintWriter p = new PrintWriter(System.out);
        int t = sc.nextInt();
        while(t-- != 0)
        {
            String bot = sc.next();
            char a[] = bot.toCharArray();
            int n = bot.length();
            HashMap<Character, Integer> freq = new HashMap<>();
            freq.put('R',0);
            freq.put('P',0);
            freq.put('S',0);
            for(char i : a)
            {
                if(freq.containsKey(i))
                {
                    int value = freq.get(i);
                    freq.put(i,value+1);
                }
                else
                {
                    freq.put(i,1);
                }
            }
            char ans = 'R';
            if(freq.get('R') >= freq.get('P') && freq.get('R') >= freq.get('S'))
            {
                ans = 'P';
            }
            else if(freq.get('P') >= freq.get('R') && freq.get('P') >= freq.get('S'))
            {
                ans = 'S';
            }
            else
            {
                ans = 'R';
            }
            for(int i = 0; i < n; i++)
            {
                p.print(ans);
            }
            p.println();
        }
        p.close();
    }

/*
    Move to top!!
*/
    static class Foster 
    {
        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());
        }
        long nextLong() 
        {
            return Long.parseLong(next());
        }
        double nextDouble() 
        {
            return Double.parseDouble(next());
        }
        int[] intArray(int n)
        {
            int arr[] = new int[n];
            for(int i = 0; i < n; i++)
            {
                arr[i] = nextInt();
            }
            return arr;
        }
        long[] longArray(int n)
        {
            long arr[] = new long[n];
            for(int i = 0; i < n; i++)
            {
                arr[i] = nextLong();
            }
            return arr;
        }
        void print(Object... o) 
        {
            for(Object next : o)
            {
                System.out.print(next + " ");
            }
        }
        void println(Object o) 
        {
            System.out.println(o);
        }
        void watch(Object...a) throws Exception 
        {
            int i = 1;
            System.out.print("watch starts\n");
            for (Object o: a) 
            {
                boolean found = false;
                if (o.getClass().isArray()) 
                {
                    String type = o.getClass().getName().toString();
                    switch (type) 
                    {
                        case "[I":
                        {
                            int[] test = (int[]) o;
                            print(i + " : " + Arrays.toString(test));
                            break;
                        }
                        case "[[I":
                        {
                            int[][] obj = (int[][]) o;

                            print(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[J":
                        {

                            long[] obj = (long[]) o;
                            print(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[J":
                        {

                            long[][] obj = (long[][]) o;
                            print(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[D":
                        {

                            double[] obj = (double[]) o;
                            print(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[D":
                        {

                            double[][] obj = (double[][]) o;
                            print(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[Ljava.lang.String":
                        {

                            String[] obj = (String[]) o;
                            print(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[Ljava.lang.String":
                        {

                            String[][] obj = (String[][]) o;
                            print(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[C":
                        {
                            char[] obj = (char[]) o;
                            print(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[C":
                        {

                            char[][] obj = (char[][]) o;
                            print(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        default:
                        {
                            print(i + " : type not identified");
                            break;
                        }
                    }
                    found = true;
                }
                if (o.getClass() == ArrayList.class) 
                {
                    print(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == TreeSet.class) 
                {
                    print(i + " : SET = " + o);
                    found = true;
                }
                if (o.getClass() == TreeMap.class) 
                {
                    print(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == HashMap.class) 
                {
                    print(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == LinkedList.class) 
                {
                    print(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == PriorityQueue.class) 
                {
                    print(i + " : PQ = " + o);
                    found = true;
                }
                if (!found) 
                {
                    print(i + " = " + o);
                }
                i++;
            }
            print("watch ends ");
        }
    }
}