#include <bits/stdc++.h>
using namespace ::std;
template <class T>
T SQR(T N) {
  return (T)N * N;
}
template <class T>
double DIST(T a, T b) {
  return 1.0 * sqrt(SQR(double(a)) + SQR(double(b)));
}
template <class T>
bool CROSS(pair<T, T> a, pair<T, T> b, pair<T, T> c) {
  return (b.first - a.first) * (c.second - b.second) >=
         (b.second - a.second) * (c.first - b.first);
}
int px[] = {0, 1, -1, 0, -1, -1, 1, 1};
int py[] = {1, 0, 0, -1, -1, 1, -1, 1};
const double eps = 1e-9;
inline long long power(long long a, long long p, long long mod) {
  long long x = a, res = 1;
  while (p) {
    if (p & 1) res = (res * x) % mod;
    p /= 2, x = (x * x) % mod;
  }
  return res;
}
int F[207];
inline void Fail(string str) {
  string s = str;
  reverse(s.begin(), s.end());
  s = s + "#" + str;
  int len = s.length();
  for (int i = 1; i < len; ++i) {
    int j = F[i - 1];
    while (j > 0 and s[i] != s[j]) j = F[j - 1];
    if (s[i] == s[j]) ++j;
    F[i] = j;
  }
}
int main() {
  cin.tie(0);
  cout.tie(0);
  int n, m, c, d, a, b, k;
  int test;
  scanf("%d", &test);
  for (int t = 1; t <= test; ++t) {
    string str;
    cin >> str;
    a = b = c = 0, n = str.length();
    for (int i = 0; i < n; ++i) {
      if (str[i] == 'R') ++a;
      if (str[i] == 'S') ++b;
      if (str[i] == 'P') ++c;
    }
    for (int i = 0; i < n; ++i)
      printf("%c", (a >= b and a >= c) ? 'P' : (b >= a and b >= c) ? 'R' : 'S');
    puts("");
  }
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace ::std;
template <class T>
T SQR(T N) {
  return (T)N * N;
}
template <class T>
double DIST(T a, T b) {
  return 1.0 * sqrt(SQR(double(a)) + SQR(double(b)));
}
template <class T>
bool CROSS(pair<T, T> a, pair<T, T> b, pair<T, T> c) {
  return (b.first - a.first) * (c.second - b.second) >=
         (b.second - a.second) * (c.first - b.first);
}
int px[] = {0, 1, -1, 0, -1, -1, 1, 1};
int py[] = {1, 0, 0, -1, -1, 1, -1, 1};
const double eps = 1e-9;
inline long long power(long long a, long long p, long long mod) {
  long long x = a, res = 1;
  while (p) {
    if (p & 1) res = (res * x) % mod;
    p /= 2, x = (x * x) % mod;
  }
  return res;
}
int F[207];
inline void Fail(string str) {
  string s = str;
  reverse(s.begin(), s.end());
  s = s + "#" + str;
  int len = s.length();
  for (int i = 1; i < len; ++i) {
    int j = F[i - 1];
    while (j > 0 and s[i] != s[j]) j = F[j - 1];
    if (s[i] == s[j]) ++j;
    F[i] = j;
  }
}
int main() {
  cin.tie(0);
  cout.tie(0);
  int n, m, c, d, a, b, k;
  int test;
  scanf("%d", &test);
  for (int t = 1; t <= test; ++t) {
    string str;
    cin >> str;
    a = b = c = 0, n = str.length();
    for (int i = 0; i < n; ++i) {
      if (str[i] == 'R') ++a;
      if (str[i] == 'S') ++b;
      if (str[i] == 'P') ++c;
    }
    for (int i = 0; i < n; ++i)
      printf("%c", (a >= b and a >= c) ? 'P' : (b >= a and b >= c) ? 'R' : 'S');
    puts("");
  }
}

```