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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeMap;



public class COVID {

	static ArrayList<Edge>[] adjList;

	static int mod;


	static class Edge implements Comparable<Edge>{
		int node,sec;long t;

		public Edge( int v, int sec, long t) {
			super();
			this.node = v;
			this.sec = sec;
			this.t = t;
		}
		public int compareTo(Edge e) {
			return (int)(t-e.t);
		}


	}

	static ArrayList<String>all;
	static char[] tmp;
	static void bf (int pos,int n)
	{
		if(pos==n) {
			all.add(new String(tmp));
			return;
		}
		tmp[pos]='R';
		bf(pos+1,n);
		tmp[pos]='S';
		bf(pos+1,n);
		tmp[pos]='P';
		bf(pos+1,n);
	}
	public static int compute(String a, String b,int pos )
	{
		int c=0;
		for(int i=0;i<b.length();i++) {
			if(a.charAt((i+pos)%b.length())=='R'&&b.charAt(i)=='P')
					c++;
			if(a.charAt((i+pos)%b.length())=='S'&&b.charAt(i)=='R')
				c++;
			if(a.charAt((i+pos)%b.length())=='P'&&b.charAt(i)=='S')
				c++;
	
		}
		return c;
	}
	public static int totComp(String a, String b) {
		int sum=0;
		for(int i=0;i<a.length();i++)
			sum+=compute(a, b,i);
		return sum ;
	}
	
	public static void main(String[] args) throws Exception {

		Scanner	sc = new Scanner(System.in);
		PrintWriter pw= new PrintWriter(System.out);
//		String s=sc.next();
//		all=new ArrayList<>();
//		tmp=new char[s.length()];
//		bf(0, s.length());
//		ArrayList<String > ans=new ArrayList<>();
//		int max=0;
//		for( String b:all) {
//			int val=totComp(s, b);
//			if(val>max) {
//				max=val;
//				ans=new ArrayList<>();
//				ans.add(b);
//			}else if(val==max) {
//				ans.add(b);
//			}
//		}
//		System.out.println(ans);
//		System.out.println(ans.size());
		int t=sc.nextInt();
	h:	while(t-->0) {
		char[] s=sc.next().toCharArray();
		StringBuilder sb=new StringBuilder();
		int[] cnt=new int[3];
		for(char c: s) {
			if(c=='R')
				cnt[0]++;
			else if(c=='S')
				cnt[1]++;
			else
				cnt[2]++;
		}
		if(cnt[0]>=cnt[1]&&cnt[0]>=cnt[2]) {
			for(char c:s)
				sb.append("P");
		}else if(cnt[1]>=cnt[0]&&cnt[1]>=cnt[2]) {
			
			for(char c:s)
				sb.append("R");
		}else  {
			for(char c:s)
				sb.append("S");
	
		}
		pw.println(sb);
	
	}
		pw.flush();
		pw.close();

	}
	


	static long gcd(long a, long b) {
		return (b==0)?a:gcd(b,a%b);
	}
	static long lcm(long a, long b) {
		return a/gcd(a,b)*b;
	}
	public static int log(int n , int base) {
		int ans=0;
		while(n+1>base) {
			ans++;
			n/=base;
		}
		return ans;
	}
	static int pow(int b,long e) {
		int ans=1;
		while(e>0) {
			if((e&1)==1)
				ans=(int)((ans*1l*b));
			e>>=1;{

			}
			b=(int)((b*1l*b));
		}
		return ans;
	}
	static long powmod(long b,long e, int mod) {
		long ans=1;
		b%=mod;
		while(e>0) {
			if((e&1)==1)
				ans=(int)((ans*1l*b)%mod);
			e>>=1;
			b=(int)((b*1l*b)%mod);
		}
		return ans;
	}
	public static long add(long a, long b) {
		return (a+b)%mod;
	}
	public static long mul(long a, long b) {
		return ((a%mod)*(b%mod))%mod;
	}










	static class Pair implements Comparable<Pair>{

		int  x;int y;



		public Pair(int a,int b) {
			this.x=a;y=b;
		}









		public int compareTo(Pair o) {
			return (x==o.x)?((y>o.y)?1:(y==o.y)?0:-1):((x>o.x)?1:-1);
			//		return y-o.y;
		}


		@Override




		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}


		@Override


		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}






	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}

		public long[] nextLongArr(int n) throws IOException {
			long[] arr=new long[n];
			for(int i=0;i<n;i++)
				arr[i]=nextLong();
			return arr;
		}
		public int[] nextIntArr(int n) throws IOException {
			int[] arr=new int[n];
			for(int i=0;i<n;i++)
				arr[i]=nextInt();
			return arr;
		}
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine()," ,");
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}


		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
}