Matcom Online Grader

ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.

MOG Training #3

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

F - Hay Bales

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#

Time & Memory limits: (details)

Peter has lined up hay bales. Some hay bales contain parasites and he wants to move the infected hay bales to the back of the sequence, to minimize the chance that the parasites spread. To sort the haybales, he repeatedly takes out any three consecutive hay bales and puts them back in sorted order. Your task is to calculate the minimum number of operations Peter has to execute to sort the sequence.

(Picture by stanze)

Input

The input contains a single string $s$ ($3 \leq |s| \leq 500$), the sequence of hay bales. Each character of $s$ is either $\texttt{C}$ (for a clean hay bale) or $\texttt{P}$ (for an infected one).

Output

The output must contain one integer, the minimum number of steps Peter has to execute.

Sample test(s)

Input

CPCC

Output

Input

PPPPCCCC

Output

Input

CCCCPPPP

Output