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.*;
     
    public class gym{
    	static void main() throws Exception{
    		char[]in=sc.nextLine().toCharArray();
    		int r=0,s=0,p=0;
    		for(char c:in) {
    			r+=c=='R'?1:0;
    			s+=c=='S'?1:0;
    			p+=c=='P'?1:0;
    		}
    		char ans;
    		if(r>=s && r>=p) {
    			ans='P';
    		}
    		else {
    			if(s>=p && s>=r) {
    				ans='R';
    			}
    			else {
    				ans='S';
    			}
    		}
    		for(int i=0;i<in.length;i++)pw.print(ans);
    		pw.println();
    	}
    	public static void main(String[] args) throws Exception{
    		sc=new MScanner(System.in);
    		pw = new PrintWriter(System.out);
    		int tc=1;
    		tc=sc.nextInt();
    		while(tc-->0)
    			main();
    		pw.flush();
    	}
    	static PrintWriter pw;
    	static MScanner  sc;
    	static class MScanner {
    		StringTokenizer st;
    		BufferedReader br;
    		public MScanner(InputStream system) {
    			br = new BufferedReader(new InputStreamReader(system));
    		}
     
    		public MScanner(String file) throws Exception {
    			br = new BufferedReader(new FileReader(file));
    		}
     
    		public String next() throws IOException {
    			while (st == null || !st.hasMoreTokens())
    				st = new StringTokenizer(br.readLine());
    			return st.nextToken();
    		}
    		public int[] intArr(int n) throws IOException {
    	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
    	        return in;
    		}
    		public long[] longArr(int n) throws IOException {
    	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
    	        return in;
    		}
    		public int[] intSortedArr(int n) throws IOException {
    	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
    	        shuffle(in);
    	        Arrays.sort(in);
    	        return in;
    		}
    		public long[] longSortedArr(int n) throws IOException {
    	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
    	        shuffle(in);
    	        Arrays.sort(in);
    	        return in;
    		}
    		public Integer[] IntegerArr(int n) throws IOException {
    	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
    	        return in;
    		}
    		public Long[] LongArr(int n) throws IOException {
    	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
    	        return in;
    		}
    		public String nextLine() throws IOException {
    			return br.readLine();
    		}
     
    		public int nextInt() throws IOException {
    			return Integer.parseInt(next());
    		}
     
    		public double nextDouble() throws IOException {
    			return Double.parseDouble(next());
    		}
     
    		public char nextChar() throws IOException {
    			return next().charAt(0);
    		}
     
    		public long nextLong() throws IOException {
    			return Long.parseLong(next());
    		}
     
    		public boolean ready() throws IOException {
    			return br.ready();
    		}
     
    		public void waitForInput() throws InterruptedException {
    			Thread.sleep(3000);
    		}
    	}
    	static void shuffle(int[]in) {
    		for(int i=0;i<in.length;i++) {
    			int idx=(int)(Math.random()*in.length);
    			int tmp=in[i];
    			in[i]=in[idx];
    			in[idx]=tmp;
    		}
    	}
    	static void shuffle(long[]in) {
    		for(int i=0;i<in.length;i++) {
    			int idx=(int)(Math.random()*in.length);
    			long tmp=in[i];
    			in[i]=in[idx];
    			in[idx]=tmp;
    		}
    	}
    }