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