剪刀石头布是一款适合两个玩家的游戏。它是按回合进行的。在每一轮中,每个玩家选择三种动作之一:石头、布或剪刀。根据所选的动作,会发生以下情况:
- 如果一名玩家选择石头,另一名玩家选择纸,则选择纸的玩家获胜并获得一分;
- 如果一名玩家选择剪刀,另一名玩家选择布,则选择剪刀的玩家获胜并获得一分;
- 如果一名玩家选择剪刀,另一名玩家选择石头,则选择石头的玩家获胜并获得一分;
- 如果两个玩家选择相同的动作,则没有人获胜,也没有人得分。
Monocarp 决定与机器人对战。在游戏过程中,Monocarp 注意到机器人的行为非常可预测:
- 第一轮选择Rock;
- 在除第一轮之外的每一轮中,它都会选择击败对手上一轮动作的动作(例如,如果在上一轮中对手玩剪刀,那么机器人现在选择石头)。
Monocarp 有一个最喜欢的字符串 $$$s$$$,由字符 R、P 和/或 S 组成。Monocarp 决定与机器人进行一系列回合。不过,他希望满足以下两个条件:
- 最终得分对 Monocarp 有利(即,他赢得的回合数严格大于机器人获胜的回合数);
- 字符串 $$$s$$$ 在机器人的移动序列中显示为连续子字符串(其中 R 表示 Rock,P 表示 Paper,S 表示 Scissors)。
帮助 Monocarp 计算他需要与机器人对战的最少回合数才能满足上述两个条件。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$),由字符 R、P 和/或 S 组成。
对输入的附加约束:所有测试用例中字符串 $$$s$$$ 的长度总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - Monocarp 需要与机器人对战以满足上述两个条件的最小轮数。
示例
输入 #1
7 SS R RPS RPPP SPPRSP PPP PR
输出 #1
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 胜出。