건초 더미

피터가 건초 더미를 한 줄로 세워 놓았다. 그중 몇 더미에는 기생충이 있다. 기생충이 퍼지는 것을 최대한 막으려고 피터는 감염된 더미를 줄의 뒤쪽으로 보내려고 한다.

한 번의 작업에서 피터는 연속한 세 더미를 골라 꺼낸 다음, 깨끗한 더미가 앞에 오고 감염된 더미가 뒤에 오도록 정렬해서 원래 자리에 다시 넣는다. 모든 깨끗한 더미가 모든 감염된 더미보다 앞에 서면 줄이 정렬된 것이다.

줄을 정렬하려고 피터가 실행해야 하는 작업 횟수의 최솟값을 구하라.

첫째 줄에 건초 더미의 배열을 나타내는 문자열 $s$가 주어진다 ($3 \le |s| \le 500$). $s$의 각 문자는 깨끗한 더미를 뜻하는 C 또는 감염된 더미를 뜻하는 P다. 문자는 더미가 줄에 서 있는 순서대로 주어진다.

피터가 실행해야 하는 작업 횟수의 최솟값을 정수 하나로 출력한다.