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.PrintWriter;
import java.util.Scanner;

public class Second {
	static Scanner sc =new Scanner(System.in);
	static PrintWriter out=new PrintWriter(System.out);
	
	public static void BerlandPoker() {
		int t=sc.nextInt();
		for(int o=0;o<t;o++) {
			int n=sc.nextInt();
			int m=sc.nextInt();
			int k=sc.nextInt();
			int numOfCards=n/k;
			if(numOfCards>=m)
				System.out.println(m);
			else if(n==m)
				System.out.println(0);
			else {
				k--;
				m-=numOfCards;
				if(m<=k) {
					System.out.println(numOfCards-1);
				}
				else {
				int d=m/k;
				int mod=m%k;
				if(mod!=0)
			      System.out.println(numOfCards-(d+1));
				else
				  System.out.println(numOfCards-(d));


				}
			}
		}
	}
	
	public static void TheatreSquare() {
		double n=sc.nextInt();
		double m=sc.nextInt();
		double a=sc.nextInt();
		System.out.println((long)(((long)Math.ceil(n/a))*((long)Math.ceil(m/a))));
		
	}
	
	public static void NewTheatreSquare() {
		int t=sc.nextInt();
		for(int o=0;o<t;o++) {
			int n=sc.nextInt();
			int m=sc.nextInt();
			int x=sc.nextInt();
			int y=sc.nextInt();
			sc.nextLine();
			int c=0;
			char[][]grid=new char[n][m];
			for(int i=0;i<n;i++) {
				grid[i]=sc.nextLine().toCharArray();
			}
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(grid[i][j]=='.') {
						if(j<m-1) {
							if(grid[i][j+1]=='.'&&y<=2*x) 
								c+=y;						
							else if(grid[i][j+1]=='.') 
							    c+=(2*x);
							else if(grid[i][j+1]!='.')
								c+=x;
							j++;
						}
						else {
							c+=x;
						}

					}
				}
			}
			System.out.println(c);
		}
	}
	
	public static void ThreeIndices() {
		int t=sc.nextInt();
		for(int o=0;o<t;o++) {
			int n=sc.nextInt();
			int p[]=new int[n];
			for(int i=0;i<n;i++)
				p[i]=sc.nextInt();
			boolean f=false;
			int a=0;
			for(int i=0;i<n-2&&!f;i++) {
				if(p[i]<p[i+1]&&p[i+2]<p[i+1]) {
					f=true;a=i;
				}
			}
			if(f) {System.out.println("Yes");
			System.out.println((int)(a+1)+" "+(int)(a+2)+" "+(int)(a+3)+" ");
			}
			
			else System.out.println("No");
		}
	}
	
	public static void UniversalSolution() {
		int t=sc.nextInt();
		sc.nextLine();
		for(int o=0;o<t;o++) {
			String s=sc.nextLine();
			int Pc=0;
			int Rc=0;
			int Sc=0;
			for(int i=0;i<s.length();i++) {
				if(s.charAt(i)=='R')
					Rc++;
				else if(s.charAt(i)=='P')
					Pc++;
				else
					Sc++;
			}
			int m=Math.max(Pc, Math.max(Rc, Sc));
			for(int i=0;i<s.length();i++) {
				if(m==Pc) {
					out.print('S');
				}
				else if(m==Rc)
					out.print('P');
				else if(m==Sc)
					out.print('R');
				
				
			}
			out.println();
			out.flush();
		}
	}
	
	
	
	

	public static void main(String[] args) {
		//BerlandPoker();
		//TheatreSquare();
		//NewTheatreSquare();
		//ThreeIndices();
		UniversalSolution();

	}

}
