E. 石头剪刀布机器人 每个测试时间限制 $2$ 秒 每个测试内存限制 $512$ MB

石头剪刀布是一款两人游戏。游戏以回合制进行。在每一轮中，每位玩家从三种手势中选择一种：石头、布或剪刀。根据所选的手势，会出现以下情况：

如果一方出石头，另一方出布，则出布的玩家获胜并得 $1$ 分；

如果一方出剪刀，另一方出布，则出剪刀的玩家获胜并得 $1$ 分；

如果一方出剪刀，另一方出石头，则出石头的玩家获胜并得 $1$ 分；

如果双方出相同的手势，则无人得分。

Monocarp 决定与一个机器人对战。在对战过程中，Monocarp 发现机器人的行为非常可预测：

在第一轮中，机器人会出石头；

在之后的每一轮中，机器人会选择能够击败对手上一轮手势的手势（例如，如果上一轮对手出了剪刀，那么机器人这一轮就会出石头）。

Monocarp 有一个最喜欢的字符串 s s，由字符 R、P 和/或 S 组成。Monocarp 决定与机器人进行一系列回合。但他希望同时满足以下两个条件：

最终比分对 Monocarp 有利（即他获胜的轮数严格大于机器人获胜的轮数）；

字符串 s s 作为连续子串出现在机器人的手势序列中（其中 R 代表石头，P 代表布，S 代表剪刀）。

请帮助 Monocarp 计算他最少需要与机器人进行多少轮游戏，才能同时满足上述两个条件。

输入 第一行包含一个整数 t t ($1 \le t \le 10^4$) —— 测试用例的数量。 每个测试用例仅有一行，包含一个字符串 s s ($1 \le |s| \le 2 \cdot 10^5$)，由字符 R、P 和/或 S 组成。 输入的额外限制：所有测试用例中字符串 s s 的长度之和不超过 $2 \cdot 10^5$。

输出 对于每个测试用例，输出一个整数 —— Monocarp 需要与机器人进行的最少轮数，以便同时满足上述两个条件。

样例输入

text $7$ SS R RPS RPPP SPPRSP PPP PR 样例输出

text $3$ $1$ $3$ $6$ $7$ $5$ $3$ 说明 在第一个例子中，Monocarp 可以出 PPR，此时机器人的手势序列为 RSS，比分为 $2$:$1$，Monocarp 获胜。 在第二个例子中，Monocarp 可以出 P，此时机器人的手势序列为 R，比分为 $1$:$0$，Monocarp 获胜。 在第三个例子中，Monocarp 可以出 RPR，此时机器人的手势序列为 RPS，比分为 $1$:$0$，Monocarp 获胜。 在第四个例子中，Monocarp 可以出 RRRSPR，此时机器人的手势序列为 RPPPRS，比分为 $3$:$2$，Monocarp 获胜。 在第五个例子中，Monocarp 可以出 PRRSPRS，此时机器人的手势序列为 RSPPRSP，比分为 $6$:$1$，Monocarp 获胜。 在第六个例子中，Monocarp 可以出 PRRRS，此时机器人的手势序列为 RSPPP，比分为 $3$:$2$，Monocarp 获胜。 在第七个例子中，Monocarp 可以出 RSR，此时机器人的手势序列为 RPR，比分为 $1$:$0$，Monocarp 获胜。