Joy 走在貝克街上，突然亡靈出現在他面前，亡靈放出的閃光實在太亮，導致 Joy 無法順利向前走。

亡靈說只要 Joy 能夠在和自己比的 \(n\) 次猜拳中贏的次數比輸的次數多，就算 Joy 贏，而她就會到別的地方閃瞎別人。

亡靈知道 Joy 有看穿人心的能力，即 Joy 會知道自己的 \(n\) 個拳依序是什麼，因此她追加了一個條件：

Joy 必須在開始猜拳前決定一個正整數 \(k\) 和 \(k\) 個拳。

接下來 Joy 的 \(n\) 次猜拳就會是這 \(k\) 個拳一直循環。

例如：\(n=11,k=4\)，\(k\) 個拳為 SRPR，則 Joy 出的拳將會是 SRPRSRPRSRP，其中 R,S,P 依序代表石頭、剪刀、布。

當然如果直接選 \(k=n\) 就沒意義了，因此她也要求 Joy 選的 \(k\) 必須要是最小能有辦法贏過她的 \(k\)，也就是 Joy 所選擇的 \(k\) 必須要存在 \(k\) 個拳循環能贏過她。

亡靈相信 Joy 想不出答案來，如此一來就能一直閃瞎 Joy。

請你幫 Joy 找出這個最小的 \(k\) 以及 \(k\) 個拳。

Input

第一行輸入一個正整數 \(t\)，代表有幾個子測資。

\(1\le t\le 100\)

對於每筆子測資：

第一行輸入一個正整數 \(n\)。

\(1\le n\le 2\cdot10^5\)

第二行輸入一個長度為 \(n\) 的字串 \(s\)，代表亡靈依序會出的 \(n\) 個拳，其中 R,S,P 依序代表石頭、剪刀、布。保證 \(s\) 僅由大寫英文字母 R,P,S 組成。

保證 \(n\) 的總和不超過 \(2\cdot 10^5\)。

Output

對於每筆子測資：

第一行輸出一個正整數 \(k\) 代表。

第二行輸出一個長度為 \(k\) 的字串，代表循環的 \(k\) 個拳，其中字串僅能由大寫英文字母 R,S,P 組成，R,S,P 依序代表石頭、剪刀、布。

如果有多種滿足條件的 \(k\) 個拳，請輸出任意一種。

Constraints

第 \(1\) 組測資, 亡靈只會出剪刀 \((5\text{%})\)

第 \(2\) 組測資, 亡靈只會出剪刀跟石頭。 \((7\text{%})\)

第 \(3\) 組測資, \(n\) 不為 \(3\) 的倍數。 \((11\text{%})\)

第 \(4\) 組測資, \(n\le 2000\)。 \((35\text{%})\)

第 \(5\) 組測資, 沒有其他限制。 \((42\text{%})\)

Sample Input 1

3
2
PS
6
RPSSPR
9
RPSRPSRPS

Sample Output 1

1
S
3
PSR
2
PS

Notes

亡靈的故事(改寫自 Joylintp 《相約貝克街》)：

在一個名為發財市的都市裡，人人都有一個發財夢。

有些人正努力著挖石油，有些人則想要經營國際級的遊樂園，也有些人腳踏實地的讀著書，靠著考試一步一步升學，最後出社會完成自己的發財夢—玉鈴便是一位這樣的學生。

在經過數個月的努力後，他總算考上了理想的大學，準備離開發財市前往北部就讀大學。

在抵達北部後，她打算和一位許久不見的朋友見面，他們相約在一條名為「貝克街」的街道上見面。

但是在那刻到來之前，她就把自己閃死了，成為我們熟知的亡靈。

從此她時不時會在貝克街上出沒，閃瞎所有遇到的人。