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>
#include <bits/stdc++.h>
using namespace std;
bool isSubSequence(string str1, string str2, int m, int n);
int CEIL(int a, int b);
bool isPrime(int x);
int mod_exp(long long x, unsigned int y, int p);
int gcd(int a, int b);
vector<int> Divisors(int n);
int getMSB(int n);
void Yes() { cout << "YES" << '\n'; }
void No() { cout << "No" << '\n'; }
void solve() {
  string s;
  cin >> s;
  int n = s.length();
  int r = count(s.begin(), s.end(), 'R'), p = count(s.begin(), s.end(), 'P'),
      sc = count(s.begin(), s.end(), 'S');
  string answer = "";
  string ans = "";
  for (int i = 0; i < n; i++) {
    if (max(r, max(p, sc)) == r) {
      answer += 'P';
    } else if (max(r, max(p, sc)) == sc) {
      answer += 'R';
    } else if (max(r, max(p, sc)) == p) {
      answer += 'S';
    }
  }
  cout << answer << '\n';
}
int main() {
  auto start = std::chrono::system_clock::now();
  int t;
  scanf("%d", &t);
  while (t--) solve();
  auto end = std::chrono::system_clock::now();
  std::chrono::duration<double> elapsed_seconds = end - start;
  std::time_t end_time = std::chrono::system_clock::to_time_t(end);
  return 0;
}
bool isSubSequence(string str1, string str2, int m, int n) {
  int j = 0;
  for (int i = 0; i < n && j < m; i++)
    if (str1[j] == str2[i]) j++;
  return (j == m);
}
int CEIL(int a, int b) {
  if (a % b == 0)
    return a / b;
  else
    return (a / b) + 1;
}
bool isPrime(int x) {
  if (x <= 1) return false;
  for (int i = 2, sqroot = sqrt(x); i <= sqroot; i++)
    if (x % i == 0) return false;
  return true;
}
int mod_exp(long long x, unsigned int y, int p) {
  int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
vector<int> Divisors(int n) {
  vector<int> div;
  for (int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        div.push_back(i);
      else {
        div.push_back(i);
        div.push_back(n / i);
      }
    }
  }
  return div;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int getMSB(int n) {
  if (n == 0) return 0;
  int msb = 0;
  n = n / 2;
  while (n != 0) {
    n = n / 2;
    msb++;
  }
  return msb;
}
