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.math.BigDecimal;
import java.math.MathContext;
import java.util.*;


/*
 * @author: Ramanqul
 * */
public class Main {
    private static boolean USE_TEST_CASES = true;
    private static final double EPS = .000000001;

    private static String repeat(char c, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<n;i++) {
            sb.append(c);
        }
        return sb.toString();
    }

    private static void solve(final int testCase, MyScanner in, PrintWriter out) {
        String s = in.nextLine();
        int n = s.length();

        int R = 0, S = 0, P = 0;

        for (int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            if (c == 'R') {
                R++;
            } else if (c == 'S') {
                S++;
            } else {
                P++;
            }
        }

        if (R >= Math.max(S, P)) {
            out.println(repeat('P', n));
        } else if (S >= Math.max(R, P)) {
            out.println(repeat('R', n));
        } else {
            out.println(repeat('S', n));
        }

    }



    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int t = 1;

        if (USE_TEST_CASES) {
            t = sc.nextInt();
        }

        for (int i=0;i<t;i++) {
            solve(i, sc, out);
        }
        out.close();
    }

    private static class Pair<A,B> {
        public A first;
        public B second;
        public Pair(A first, B second) {
            this.first = first;
            this.second = second;
        }
    }

    private static class Triple<A,B,C> {
        public A first;
        public B second;
        public C third;

        public Triple(A first, B second, C third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }
    }

    private static class H {
        public static void readArray(MyScanner in, int a[], int n) {
            for (int i=0;i<n;i++) {
                a[i] = in.nextInt();
            }
        }

        public static boolean isUnique(int ... nums) {
            Set<Integer> s = new HashSet<>();
            for (int i:nums) {
                if (s.contains(i)) {
                    return false;
                }
                s.add(i);
            }

            return true;
        }


        public static Pair<Integer, Integer>[] readIntPairs(MyScanner in, int n) {
            Pair[] pairs = new Pair[n];
            for (int i=0;i<n;i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                pairs[i] = new Pair<Integer, Integer>(x, y);
            }

            return pairs;
        }

        public static List<Integer> dfs(int start, List<Integer>[] adj) {
            boolean v[] = new boolean[adj.length+1];

            List<Integer> res = new ArrayList<>();

            Stack<Integer> st = new Stack<>();

            st.push(start);

            while (!st.isEmpty()) {
                int x = st.pop();
                if (!v[x]) {
                    res.add(x);
                    boolean allVisited = true;
                    for (int e: adj[x]) {
                        if (!v[e]) {
                            st.push(e);
                            allVisited = false;
                        }
                    }

                    if (allVisited) {
                        break;
                    }

                    v[x] = true;
                } else {
                    break;
                }
            }

            return res;
        }

        public static long gcd(long a, long b) {
            if (a == 0) {
                return b;
            }

            return gcd(b%a, a);
        }

        public static long lcm(long a, long b) {
            return (a * b) / gcd(a,b);
        }
    }

    private static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public MyScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                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());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
}