SP31884 RPSWAR - RPS Warfare

多瑙河低地以其肥沃的土地而闻名于世。很久以前，这里坐落着 **N** 个王国。正如优秀的王国所常做的那样，它们为自己的军队选择了最精良的武器以备战时之需。 古时候，多瑙河的军械库中只存有三种武器可供选择：火箭发射器、手枪和剑。装备火箭发射器的军队能够轻松击败那些配备剑的对手；然而他们却无法对抗使用手枪的军队。与此同时，手枪为主的军队无法匹敌挥舞剑的军队。因此，我们可以得出结论：火箭发射器胜剑，剑胜手枪，手枪胜火箭发射器。 为什么前两段都在描述这些王国和它们的武器呢？就是因为这些王国持续不断地互相征战！每个王国每年都会与其相邻的两个王国交战（如果位于最左边或最右边的王国，只会有一个邻国）。每场战争持续整整一年，胜利的一方可以占领其敌人的一块领土。紧接着，新一轮的战争又开始了。 现在，请你给出第 0 年时多瑙河沿岸王国的武器配置——用 **N** 个字符表示每个王国所选择的武器。在接下来的每一年，每个王国都会与其邻国交战。如果王国 **a** 与王国 **b** 交战，而 **a** 的武器胜过 **b**，那么在年末，**a** 将占领 **b** 的一块领土（一个字符）。如果两个王国同时要占领同一块领土，它们将通过石头剪刀布的方式决定谁获得此领土。 经过若干年后，最终会只剩下一种武器被所有剩余的王国所使用。找出这种武器是什么。

第一行输入一个整数 **T**，表示有多少组测试用例。接下来是 **T** 组测试用例。 每组测试用例的第一行含有一个整数 **N**，表示多瑙河沿岸的王国数量。第二行包含 **N** 个字符，分别表示每个王国选择的武器：**R** 表示火箭发射器，**P** 表示手枪，**S** 表示剑。 输入文件中的所有 **N** 的总和不会超过 $2 \times 10^6$。 **注意：由于输入数据量较大，请确保高效读取。**

对于每组测试用例，输出「Case **x**:」，其中 **x** 是测试用例的编号（从 1 开始），后接一个字符 **R**、**P** 或 **S**，表示最终征服整个多瑙河沿岸的武器。 **本翻译由 AI 自动生成**