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

public class c1 {
    public static void main(String[] args) {
        MyScanner scan = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));

//        int t=1;
        int t=scan.nextInt();
        while(t-->0) {

            String[] s=scan.nextLine().split("");
            HashMap<String,Integer> choice=new HashMap<>();
            for(int c=0;c<s.length;c++) {
                if(!choice.containsKey(s[c])) {
                    choice.put(s[c],1);
                } else {
                    choice.put(s[c],choice.get(s[c])+1);
                }
            }
            int max=0;
            String amax="";
            for(String key:choice.keySet()) {
                if(choice.get(key)>max) {
                    max=choice.get(key);
                    amax=key;
                }
            }
            String print="";
            if(amax.equals("R")) print="P";
            else if(amax.equals("P")) print="S";
            else print="R";
            for(int c=0;c<s.length;c++) out.print(print);
            out.println();
        }
        out.close();
    }

    //node
    static class Node implements Comparable<Node> {
        public int x,y;
        public Node(int x,int y) {
            this.x=x;
            this.y=y;
        }

        public int compareTo(Node other) {
            if(this.x==other.x) return 0;
            else if(this.x>other.x) return 1;
            else return -1;
        }

        public boolean equals(Node other) {
            return this.x==other.x;
        }

//        public int compareTo(Node other) {
//            if(this.y==other.y) return 0;
//            else if(this.y>other.y) return 1;
//            else return -1;
//        }
//
//        public boolean equals(Node other) {
//            return this.y==other.y;
//        }
    }
    //edge
    static class Edge implements Comparable<Edge> {
        public Node a,b;
        public int weight;

        public Edge(Node a,Node b,int weight) {
            this.a=a;
            this.b=b;
            this.weight=weight;
        }

        public int compareTo(Edge other) {
            if(this.weight==other.weight) return 0;
            else if(this.weight>other.weight) return 1;
            else return -1;
        }
    }

    //util
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        if (a == 0)
            return b;
        return (a > b) ? gcd(a % b, b) : gcd(a, b % a);
    }

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

    public static ArrayList<Integer> getPrimes(int n) {
        boolean prime[]=new boolean[n+1];
        Arrays.fill(prime,true);
        for (int p=2;p*p<=n;p++) {
            if (prime[p]) {
                for (int i=p*2;i<=n;i+=p) {
                    prime[i]=false;
                }
            }
        }
        ArrayList<Integer> primeNumbers=new ArrayList<Integer>();
        for (int i = 2; i <= n; i++) {
            if (prime[i]) {
                primeNumbers.add(i);
            }
        }
        return primeNumbers;
    }

    public static boolean isPrime(int a) {
        if (a == 0 || a == 1) {
            return false;
        }
        if (a == 2) {
            return true;
        }
        for (int i = 2; i < Math.sqrt(a) + 1; i++) {
            if (a % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static ArrayList<Integer> getDivisors(int n) {
        ArrayList<Integer> div = new ArrayList<Integer>();
        for (int i=1;i*i<=n;i++) {
            if (n%i==0) {
                div.add(i);
                if (n/i!=i)
                    div.add(n/i);
            }
        }
        return div;
    }

    //scanner
    public static PrintWriter out;

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

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

        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;
        }
    }
}