Educational Codeforces Round 91 (Rated for Div. 2) B. Universal Solution（思维）

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=s1s2…sns=s1s2…sn of length nn where each letter is either R, S or P.

While initializing, the bot is choosing a starting index pospos (1≤pos≤n1≤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 sposspos :

• if sposspos is equal to R the bot chooses "Rock";
• if sposspos is equal to S the bot chooses "Scissors";
• if sposspos is equal to P the bot chooses "Paper";

In the second round, the bot's choice is based on the value of spos+1spos+1 . In the third round — on spos+2spos+2 and so on. After snsn the bot returns to s1s1 and continues his game.

You plan to play nn rounds and you've already figured out the string ss but still don't know what is the starting index pospos . But since the bot's tactic is so boring, you've decided to find nn choices to each round to maximize the average number of wins.

In other words, let's suggest your choices are c1c2…cnc1c2…cn and if the bot starts from index pospos then you'll win in win(pos)win(pos) rounds. Find c1c2…cnc1c2…cn such that win(1)+win(2)+⋯+win(n)nwin(1)+win(2)+⋯+win(n)n is maximum possible.

Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000 ) — the number of test cases.

Next tt lines contain test cases — one per line. The first and only line of each test case contains string s=s1s2…sns=s1s2…sn (1≤n≤2⋅1051≤n≤2⋅105 ; si∈{R,S,P}si∈{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⋅1052⋅105 .

Output

For each test case, print nn choices c1c2…cnc1c2…cn to maximize the average number of wins. Print them in the same manner as the string ss .

If there are multiple optimal answers, print any of them.

Example

Input

Copy

3

RRRR

RSP

S

Output

Copy

PPPP

RSP

R

朴素的想法是，复制一份字符串拼接到末尾，然后枚举位置。但仔细一想，由于是循环的，根据概率，答案字符串的每个位置都应该放克制原串出现频率最高的字符的字符。所以扫一遍原串然后构造即可。

#include <bits/stdc++.h>
using namespace std;
string ss;
int main(){
    int t;
    cin >> t;
    while(t--){
        cin >> ss;
        int cnt[3];
        cnt[0] = cnt[1] = cnt[2] = 0;
        for(int i = 0; i < ss.size(); i++){
            if(ss[i] == 'R')cnt[0]++;
            else if(ss[i] == 'S') cnt[1]++;
            else if(ss[i] == 'P') cnt[2]++;
        }
        int mmax = max(cnt[0], max(cnt[1], cnt[2]));
        char c;
        if(cnt[0] == mmax) c = 'P';
        else if(cnt[1] == mmax) c = 'R';
        else if(cnt[2] == mmax) c = 'S';
        for(int i = 0; i < ss.size(); i++) putchar(c);
        cout << endl;
    }
    return 0;
}