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;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
  cout << p.first << ' ' << p.second;
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++)
    cout << v[i] << (i == (int)v.size() - 1 ? "" : " ");
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  for (auto i = s.begin(); i != s.end(); ++i)
    cout << *i << (i == prev(s.end()) ? "" : " ");
  return os;
}
string rem(string second) {
  if (second[second.size() - 1] == '\r') second.erase(second.size() - 1);
  return second;
}
vector<string> split(string second, char delim) {
  replace(second.begin(), second.end(), delim, ' ');
  stringstream ss(second);
  string buf;
  vector<string> v;
  while (ss >> buf) v.push_back(buf);
  return v;
}
long long fpowm(long long x, unsigned long long y,
                unsigned long long p = LLONG_MAX) {
  long long 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;
}
inline vector<int> ints(int x) {
  vector<int> A(x);
  for (int i = 0; i < (x); i++) cin >> A[i];
  return A;
}
inline vector<long long> lls(int x) {
  vector<long long> A(x);
  for (int i = 0; i < (x); i++) cin >> A[i];
  return A;
}
inline vector<string> strs(int x) {
  vector<string> A(x);
  for (int i = 0; i < (x); i++) cin >> A[i];
  return A;
}
struct chsh {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
const int MOD = 1000000007;
const double EPS = 1e-6;
const int MAXN = -1;
int tc() {
  int N;
  string A;
  cin >> A;
  N = (int)A.size();
  vector<pair<int, int> > cnt(3);
  for (int i = 0; i < (N); i++) {
    if (A[i] == 'R')
      cnt[0].first++;
    else if (A[i] == 'P')
      cnt[1].first++;
    else
      cnt[2].first++;
  }
  cnt[0].second = 'R';
  cnt[1].second = 'P';
  cnt[2].second = 'S';
  sort(cnt.begin(), cnt.end());
  char tg = '~';
  if (cnt[2].second == 'R') tg = 'P';
  if (cnt[2].second == 'P') tg = 'S';
  if (cnt[2].second == 'S') tg = 'R';
  (cout << string(N, tg) << '\n');
  ;
  return 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) tc();
  return 0;
}
