P12950 [GCJ Farewell Round #1] Untie

一群人围坐成一圈，正在玩一个特殊版本的石头剪刀布游戏。在这个游戏中，每个人秘密选择石头、布或剪刀，然后所有人同时向其他人展示自己的选择。每个人会将自己的选择与左右两位邻居进行比较，可能分别对每位邻居获胜、落败或平局。只有当两人选择相同时才会出现平局。 你希望调整游戏结果，使得没有任何相邻两人出现平局。对于每位玩家，你可以选择保留其原有选择，或者要求他们更改为另外两个选项中的任意一个（由你决定改为哪个）。为了确保在调整后所有相邻玩家的选择都不相同，最少需要改变多少人的选择？

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 行，每行表示一个测试用例，包含一个字符串 $\mathbf{C}$。$\mathbf{C}$ 的第 $i$ 个字符表示顺时针方向第 $i$ 个人的初始选择，其中大写字母 $\mathbf{R}$ 表示石头，$\mathbf{P}$ 表示布，$\mathbf{S}$ 表示剪刀。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是为了确保相邻玩家最终选择不同所需的最少改变次数。

**样例解释** 在样例 #1 中，存在一对相邻玩家都选择布（输入的首尾字符），以及另一对相邻玩家都选择剪刀。因此至少需要两次改变。其中一种实现方式是：将最左侧的布改为剪刀，最右侧的剪刀改为石头，得到 SRSRP。 在样例 #2 中，所有 7 位参与者都选择了石头。如果最多改变 3 次选择，那么至少会剩下 4 个石头，其中至少有两个是相邻的。因此最少需要改变 4 次。其中一种实现方式是得到 PRSRPRS。 在样例 #3 中，没有任何相邻玩家出现平局，因此不需要改变。 **数据范围** - $1 \leq \mathbf{T} \leq 100$。 - $\mathbf{C}$ 的每个字符都是大写字母 $\mathbf{R}$、$\mathbf{P}$ 或 $\mathbf{S}$。 **测试集 1（9 分，可见判定）** - $3 \leq \mathbf{C}$ 的长度 $\leq 10$。 **测试集 2（20 分，可见判定）** - $3 \leq \mathbf{C}$ 的长度 $\leq 1000$。 翻译由 DeepSeek V3 完成