一群人围坐成一个圆圈，正在玩一种特殊版本的石头、剪刀、布游戏。在这个游戏中，每个人秘密地选择石头、剪刀或布，然后每个人向其他人展示自己的选择。每个人将自己的选择与左右两个邻居进行比较，并独立地与他们中的每一个进行胜、负或平局的判定。只有当两人做出相同的选择时，才会出现平局。

你希望确保没有任何游戏出现平局。对于每个玩家，你可以让他们保持原有的选择，或者要求他们改为其他两种选择中的任意一种（由你决定改为哪一种）。为了确保在做出这些更改后，任意相邻的两人之间都不会出现平局，你需要要求更改选择的最少人数是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 行。每一行代表一个测试用例，包含一个字符串 $C$。$C$ 的第 $i$ 个字符表示顺时针方向上第 $i$ 个人的初始选择，其中大写字母 $R$ 代表石头，大写字母 $P$ 代表布，大写字母 $S$ 代表剪刀。

输出格式

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

数据范围

$1 \le T \le 100$。 $C$ 中的每个字符均为大写字母 $R$、$P$ 或 $S$。

子任务 1 $3 \le$ $C$ 的长度 $\le 10$。

子任务 2 $3 \le$ $C$ 的长度 $\le 1000$。

样例

输入 1

3
PRSSP
RRRRRRR
RSPRPSPRS

输出 1

Case #1: 2
Case #2: 4
Case #3: 0

说明

在样例 1 中，有一对相邻的人都选择了布（输入的第一个和最后一个字符），还有一对都选择了剪刀。因此，我们至少需要两次更改。实现两次更改的一种方法是将最左边的布改为剪刀，将最右边的剪刀改为石头，从而得到 SRSRP。

在样例 2 中，所有 7 名参与者都选择了石头。如果我们最多更改 3 个选择，则至少还会有 4 个石头，并且其中至少有两个会是相邻的。因此，最少更改次数至少为 4。实现 4 次更改的一种方法是得到 PRSRPRS。

在样例 3 中，没有相邻的一对人出现平局，因此不需要更改。