KSA 문자열

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

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

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

문자열에는 다음과 같은 시행을 $0$회 이상 수행할 수 있다.

• 존재하는 아무 문자를 한 개 제거한다.
• 맨 앞에 아무 문자를 한 개 추가한다.
• 맨 뒤에 아무 문자를 한 개 추가한다.

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

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

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

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