The Danubian Lowland has always been a very fertile area. No wonder that a long, long time ago there were N kingdoms situated by the Danube river. As all good kingdoms do, each had chosen its favourite weapon, with which it equipped its armies in times of war.

The Danube arsenal was quite limited - in these ancient times only three weapons were available: Rocket launchers, Pistols and Swords. An army equipped with rocket launchers devastated those which challenged it with swords. At the same time, they did not stand a chance against opponents using pistols. And as you might already suspect, an army relying on pistols could not withstand the might of a sword-wielding army. Hence, we say that rocket launchers beat swords, swords beat pistols, and pistols beat rocket launchers.

Try to guess why the first two paragraphs were dedicated to kingdoms and their weapons. Exactly - these kingdoms constantly fought against each other! Each kingdom went to war with both of its neighbours every year (respectively one, if the kingdom was the left or rightmost). Every war lasted exactly one year, after which the victorious kingdom captured one enemy territory. Of course, just after that another war began.

You are given a description of the kingdoms by the Danube river - N characters representing the chosen weapon of each kingdom - in the year 0. Each year, every kingdom will go to war with its neighbouring kingdoms. If two kingdoms a and b go to war, and the weapon of kingdom a beats the weapon of kingdom b, then at the end of the year kingdom a will capture one territory (one character) of kingdom b. If two kingdoms defeat the same territory of a kingdom at once, they decide which one captures the territory by a game of rock-paper-scissors.

After some finite number of years, there will only be a single weapon which all the remaining kingdoms are using. Find out which one.

Input

The first line contains an integer 1 ≤ T ≤ 30: the number of test cases. T test cases follow.

For each case, the first line contains the integer 1 ≤ N ≤ 10⁶ - the number of kingdoms by the Danube river. The second line contains N characters representing each kingdom's chosen weapon: R for rocket launchers, P for pistols, and S for swords.

The sum of N within one input file does not exceed 2×10⁶. 

Warning - the input is quite large. Make sure to read it efficiently.

Output

For each test case, output "Case x: ", where x is the number of the test case, starting from 1, followed by the character R, P or S: the character representing the weapon which will conquer the entire river bank of Danube.

Example

Input:
2
3
RPS
7
RRRRRRP

Output:
Case 1: S
Case 2: P

In case 1, after the first year the situation will be PSS, and then after the second SSS.

In case 2, it will take the pistol-using kingdom six years, but no rocket launcher-equipped kingdom will be able to stop it.