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;
float PHI = 1.6180339;
const float PI_F = 3.14159265358979f;
long long modpow(long long x, long long n, long long m) {
  if (n == 0) return 1 % m;
  long long u = modpow(x, n / 2, m);
  u = (u * u) % m;
  if (n % 2 == 1) u = (u * x) % m;
  return u;
}
long long add(long long x, long long y, long long m) {
  x += y;
  if (x >= m) return x - m;
  return x;
}
long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) return x + 1000000007;
  return x;
}
long long inv(long long a, long long m = 998244353) {
  return modpow(a, m - 2, m);
}
long long mul(long long a, long long b, long long m) {
  return (long long)a * b % m;
}
long long nCrModp(long long n, long long r, long long p) {
  long long C[r + 1];
  memset(C, 0, sizeof(C));
  C[0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = min(i, r); j > 0; j--) C[j] = (C[j] + C[j - 1]) % p;
  }
  return C[r];
}
bool sortinrev(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.first - a.second) > (b.first - b.second);
}
vector<long long> z_function(string &s) {
  long long n = s.size();
  vector<long long> z(n);
  for (long long i = 1, l = 0, r = 0; i < n; i++) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  cout << fixed << setprecision(16);
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    map<char, long long> mp;
    for (long long i = 0; i < s.length(); i++) {
      ++mp[s[i]];
    }
    vector<char> v = {'R', 'S', 'P'};
    long long max1 = 0;
    char val = '#';
    for (char c : v) {
      if (mp[c] > max1) {
        max1 = mp[c];
        val = c;
      }
    }
    if (val == 'P') {
      for (long long i = 0; i < s.length(); i++) {
        cout << 'S';
      }
    } else if (val == 'S') {
      for (long long i = 0; i < s.length(); i++) {
        cout << 'R';
      }
    } else {
      for (long long i = 0; i < s.length(); i++) {
        cout << 'P';
      }
    }
    cout << "\n";
  }
  return 0;
}
