KSA 문자열 2

KSAAC 운영진은 모두 KSA를 사랑하기 때문에 다음 조건을 만족하는 문자열을 좋아한다.

문자열의 길이를 $N$이라고 할 때, $1 \leq i \leq N$인 모든 $i$에 대하여

•  $i$를 $3$으로 나눈 나머지가 $1$이면 $i$번째 문자는 K이다.
•  $i$를 $3$으로 나눈 나머지가 $2$이면 $i$번째 문자는 S이다.
•  $i$를 $3$으로 나눈 나머지가 $0$이면 $i$번째 문자는 A이다.

빈 문자열 또한 KSAAC 운영진이 좋아하는 문자열이다.

문자열에는 다음 시행을 $0$회 이상 할 수 있으며 매회 둘 중 하나를 선택하여 시행할 수 있다.

• 존재하는 아무 문자를 한 개 제거한다.
• 존재하는 아무 문자 한 개를 맨 앞으로 옮긴다.

주어진 문자열 $X$에 적절한 시행을 하여 $X$를 가능한 최대 길이의 KSAAC 운영진이 좋아하는 문자열로 바꾸려고 한다. 이때 필요한 시행의 최소 횟수를 구하여라.

첫 번째 줄에 문자열 $X$가 주어진다.

문자열 $X$를 가능한 최대 길이의 KSAAC 운영진이 좋아하는 문자열로 바꾸기 위한 최소 시행 횟수를 출력한다.

•  $1 \le |X| \le 5 \times 10^5$ 
•  $X_i \in \{ $ K $, $ S $, $ A $ \}$