← 返回题目列表

Codeforces · 2011/E

E. 石头剪刀布机器人

中文机器翻译题面 查看原题

剪刀石头布是一款适合两个玩家的游戏。它是按回合进行的。在每一轮中,每个玩家选择三种动作之一:石头、布或剪刀。根据所选的动作,会发生以下情况:

- 如果一名玩家选择石头,另一名玩家选择纸,则选择纸的玩家获胜并获得一分;
- 如果一名玩家选择剪刀,另一名玩家选择布,则选择剪刀的玩家获胜并获得一分;
- 如果一名玩家选择剪刀,另一名玩家选择石头,则选择石头的玩家获胜并获得一分;
- 如果两个玩家选择相同的动作,则没有人获胜,也没有人得分。

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 胜出。