CF2011E Rock-Paper-Scissors Bot

石头剪刀布是一款双人游戏。它是轮次进行的。在每一轮中，每个玩家都选择三种动作之一：石头、布或剪刀。根据所选的移动，将发生以下情况： - 如果一个玩家选择石头，另一个玩家选择布，则选择布的玩家获胜并获得一分; - 如果一个玩家选择剪刀，另一个玩家选择布，则选择剪刀的玩家获胜并获得一分; - 如果一个玩家选择剪刀，另一个玩家选择石头，则选择石头的玩家获胜并获得一分; - 如果两个玩家都选择相同的动作，则没有人获胜，也没有人得到一分。 小梦决定与机器人对战。在游戏过程中，小梦注意到机器人的行为非常可预测： - 在第一轮中，它选择了石头; - 在除第一轮之外的每一轮中，它都会选择击败对手在上一轮的移动（例如，如果在上一轮中对手下了剪刀，那么机器人现在选择石头）。 小梦有一个字符串 $s$ ，由字符 R、P 和 S 组成。小梦决定与机器人进行一系列回合。但是，他希望同时满足以下两个条件： - 最终比分对小梦有利（即，他赢得的回合数严格大于机器人赢得的回合数）; - 字符串$s$在机器人的移动序列中显示为一个连续的子字符串（其中 R 表示石头，P 表示布，S 表示剪刀）。 帮助小梦并计算他需要与机器人对战的最低回合数，以满足上述两个条件。

第一行包含一个整数$t(1 \le t \le 10^4)$— 测试用例的数量。 每个测试用例的唯一一行包含一个字符串$s(1 \le |s| \le 2⋅10^5)$，由字符 R、P 和 S 组成。 对 input 的附加约束：字符串$s$长度之和不超过$2⋅10^5$。

对于每个测试用例，打印一个整数 — 小梦需要与机器人对战的最小回合数，以满足上述两个条件。 ###### -dfg_mmnd

In the first example, Monocarp can play PPR, then the bot's moves are RSS, and the score is $ 2:1 $ in favor of Monocarp. In the second example, Monocarp can play P, then the bot's moves are R, and the score is $ 1:0 $ in favor of Monocarp. In the third example, Monocarp can play RPR, then the bot's moves are RPS, and the score is $ 1:0 $ in favor of Monocarp. In the fourth example, Monocarp can play RRRSPR, then the bot's moves are RPPPRS, and the score is $ 3:2 $ in favor of Monocarp. In the fifth example, Monocarp can play PRRSPRS, then the bot's moves are RSPPRSP, and the score is $ 6:1 $ in favor of Monocarp. In the sixth example, Monocarp can play PRRRS, then the bot's moves are RSPPP, and the score is $ 3:2 $ in favor of Monocarp. In the seventh example, Monocarp can play RSR, then the bot's moves are RPR, and the score is $ 1:0 $ in favor of Monocarp.