무승부 없애기

한 무리의 사람들이 원형으로 앉아 특별한 방식의 가위바위보를 하고 있다. 이 게임에서 각 사람은 바위, 보, 가위 중 하나를 비밀리에 선택한 뒤, 모두가 자신의 선택을 다른 모든 사람에게 공개한다. 그런 다음 각 사람은 자신의 선택을 양옆의 두 이웃과 비교하며, 각 이웃을 상대로 서로 독립적으로 이기거나, 지거나, 비길 수 있다. 비기는 유일한 경우는 두 사람이 같은 것을 선택했을 때이다.

여러분은 어떤 게임도 무승부가 되지 않도록 만들고자 한다. 각 참가자가 자신의 선택을 유지하게 하거나, 나머지 두 선택지 중 하나로 바꾸도록 요청할 수 있다(어느 것으로 바꿀지는 여러분이 정한다). 변경이 이루어진 후 이웃 사이에 무승부가 없도록 보장하기 위해 선택을 바꾸도록 요청해야 하는 사람 수의 최솟값은 얼마인가?

제한

시간 제한: 10초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{C}$의 각 문자는 대문자 R, 대문자 P, 대문자 S 중 하나이다.

테스트 세트 1 (판정 공개)

$\mathbf{C} \le 10$의 길이에 대해 $3 \le$.

테스트 세트 2 (판정 공개)

$\mathbf{C} \le 1000$의 길이에 대해 $3 \le$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄은 하나의 테스트 케이스를 나타내며 문자열 $\mathbf{C}$을 포함한다. $\mathbf{C}$의 $i$번째 문자는 시계 방향으로 $i$번째 사람의 원래 선택을 나타내며, 바위는 대문자 R, 보는 대문자 P, 가위는 대문자 S로 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 (1부터 시작하는) 테스트 케이스 번호이고, $y$는 어떤 이웃한 두 사람도 최종적으로 같은 선택을 하지 않도록 하는 데 필요한 변경 횟수의 최솟값이다.

예제 케이스 #1에서는 둘 다 보를 선택한 이웃 한 쌍(입력의 첫 번째 문자와 마지막 문자)이 있고, 둘 다 가위를 선택한 또 다른 이웃 한 쌍이 있다. 따라서 적어도 두 번의 변경이 필요하다. 두 번의 변경으로 이를 수행하는 한 가지 방법은 가장 왼쪽의 보를 가위로 바꾸고 가장 오른쪽의 가위를 바위로 바꾸어 SRSRP을 얻는 것이다.

예제 케이스 #2에서는 참가자 $7$명 모두가 바위를 선택했다. 선택을 최대 $3$개 변경하면 적어도 $4$개의 바위가 남고, 그중 적어도 두 개는 서로 이웃하게 된다. 따라서 변경 횟수의 최솟값은 적어도 $4$이다. 정확히 $4$번의 변경으로 이를 달성하는 한 가지 방법은 PRSRPRS을 얻는 것이다.

예제 케이스 #3에서는 무승부가 된 이웃 쌍이 없으므로 변경할 필요가 없다.