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.math.BigInteger;
													import java.sql.Array;
												    import java.util.ArrayList;
													import java.util.Arrays;
													import java.util.Collection;
													import java.util.Collections;
													import java.util.Comparator;
		import java.util.Deque;
		import java.util.HashMap;
				import java.util.HashSet;
				import java.util.InputMismatchException;
		import java.util.LinkedList;
		import java.util.PriorityQueue;
		import java.util.Queue;
		import java.util.Scanner;
															import java.util.Set;
															import java.util.Stack;
													import java.io.BufferedReader;
													import java.io.IOException;
													import java.io.InputStream;
													import java.io.InputStreamReader;
													import java.util.Scanner;
													import java.util.StringTokenizer;
													import java.util.TreeMap;
													import java.util.TreeSet;
												
													
													
													
													
													
													public class Main {
									
														
													
														public static void main(String[] args) {
														StringBuilder ans=new StringBuilder();
														FastReader sc=new FastReader();
														int t=sc.nextInt();
														
														while(t-->0) {
															
														StringBuilder sb=new StringBuilder(sc.next());
														StringBuilder a=new StringBuilder();
														
														
														int R=0,S=0,P=0;
														
														
														for(int i=0;i<sb.length();i++ )
														{
															if(sb.charAt(i)=='R')
																R++;
															
															if(sb.charAt(i)=='S')
																S++;
															
															if(sb.charAt(i)=='P')
																P++;
															
															
														}
														
														for(int i=0;i<sb.length();i++ )
														{
															if(R>=S&&R>=P) {
																a.append('P');
																
															}
															else	if(P>=S&&P>=R) {
																a.append('S');
																
															}
															else {
																a.append('R');
															}
															
														}
														
														
														System.out.println(a);
														
													
														
															
														}
													}
														
														
														
														
														
														
														
														//	System.out.println(max);
												
														
													
														
													
											
						//System.out.println(ans.toString());
						//main(						
													
									
							
						static void solvedfs(ArrayList<ArrayList<Integer>>adj,int n,int v,int subt[],int subtAns[],boolean []visited) {
									
									
									int count=1;
									int ans=0;
									visited[v]=true;
									for(int u:adj.get(v)) {
										
										
										if(!visited[u])
										{
											//System.out.println(v+" "+subt[v]+" "+n);
											subtAns[u]=Math.max(subtAns[u], subt[v]-subtAns[u]);
											
										solvedfs(adj, n, u, subt, subtAns, visited);			
										
										}
									}
									
								
									
									
									
									
									
								}
								
														
														
														
										static int dfs(ArrayList<ArrayList<Integer>>adj,int v,int subt[],int subtAns[],boolean []visited) {
										
											
											int count=0;
											int ans=0;
											visited[v]=true;
											for(int u:adj.get(v)) {
												
												
												if(!visited[u])
												{
													count+=ans;
													ans=Math.max(dfs(adj,u,subt,subtAns,visited),ans);
												}
											}
												subt[v]=count;
												subtAns[v]=ans;
												return ans+1;
												
											
											
											
											
											
										}
														
										
														
														
										static	int solve(ArrayList<ArrayList<Integer>>adj,int node,ArrayList<Integer>A)			
											{
												if(adj.get(node).size()==0)return 1;
												
												int count=0;
												for(int v:adj.get(node)) {
													
													count+=solve(adj,v,A);
													
												}
												
												A.set(node,count);
												return count+1;
												
												
												
											}
														
														
														
														
														
														
														
											static void dfs(String[]building,int i,int j,int n,int m, boolean visited[][]) {
												
												
												visited[i][j]=true;
												
												if(isValid(building,i+1,j,n,m,visited))
												{	visited[i+1][j]=true;
													dfs(building,i+1,j,n,m,visited);
												
												}
													if(isValid(building,i-1,j,n,m,visited))
												{
													visited[i-1][j]=true;
													dfs(building,i-1,j,n,m,visited);
												}
												 if(isValid(building,i,j+1,n,m,visited))
												{visited[i][j+1]=true;
													dfs(building,i,j+1,n,m,visited);
												}
														if(isValid(building,i,j-1,n,m,visited))
												{visited[i][j-1]=true;
													dfs(building,i,j-1,n,m,visited);
												}
												
												
												
												
											}
											static boolean isValid(String[]building,int i,int j,int n,int m, boolean visited[][])		
											{
												if(i==-1||j==-1||i==n||j==m||visited[i][j]||building[i].charAt(j)=='#')
													return false;
											return true;
											}
														
														
														
														
										static	void compute(boolean sieve[],int n) {
												
												for(int i=2;i<=n;i++) {
													if(sieve[i])continue;
													
													for(int j=2*i;j<n;j+=i)
													{
														sieve[j]=true;
													}
													
												}
													
												
												
											}
										
										static	void computeHs(boolean sieve[]) {
											int n=(int)(1e9-1e7+1);
											for(int i=1;i<n;i++) {
												if(sieve[i])continue;
												
												for(int j=2*i;j<n;j+=i)
												{
													sieve[j]=true;
												}
												
											}
											
										}
									
										
											
														
														
														static boolean isValid(StringBuilder s,int w) {
															if(w>s.length())return false;
															HashSet<Character>hs=new HashSet<Character>();
															int a[]=new int[3];
															
															for(int i=0;i<w;i++) {
															
																++a[s.charAt(i)-49];
																
															}
															
															if(a[0]>0&&a[1]>0&&a[2]>0)return true;
														
															int start=0;
															int end=w;
															
															while(end!=s.length()) {
																--a[s.charAt(start)-49];
																
																	++a[s.charAt(end)-49];
																
																			start++;
																				end++;
																				if(a[0]>0&&a[1]>0&&a[2]>0)return true;
																						
															}
															return false;
															
															
															
														}
										
														
														
														
											
									
														
											static int find(int parent[],int i) {
												
												if(parent[i]==-1)return i;
												
												return parent[i]=find(parent,parent[i]);
												
											}
											static void union(int parent[],int rank[],int s1,int s2) {
												
												if(rank[s1]>=rank[s2]) {
													
													parent[s2]=s1;
													rank[s1]+=rank[s2];
												}
												
												else {
													
													parent[s1]=s2;
													rank[s2]+=rank[s1];
												}
												
												
											}
														
														
														
														
														
														
														
														
														
														
														
											static	int solve(String S,int K) {
													
													if(K<=0)return 0;
													if(S.charAt(K-1)!=S.charAt(K))
													return 1+solve(S,K-1);
													else return solve(S,K-1);
												}
												
												
												
												
						
						
							
						static	boolean isValid(int g[][],int r,int c,int n,int m,boolean visited[][],int s) {
								if(r==-1||r==n||c==-1||c==m||visited[r][c]||g[r][c]!=s)return false;
								return true;
							}
						
												
													
																							
													
											    static class FastReader {
											        BufferedReader br;
											        StringTokenizer st;
											 
											        public FastReader()
											        {
											            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;
											        }
											    }
											 
												
													}
													
													
													
													
													    