Because the KSAAC staff love KSA, they like strings that satisfy the following conditions.

When the length of the string is $N$, for all $i$ such that $1\leq i\leq N$

• If the remainder after dividing $i$ by $3$ is $1$, the $i$-th character is K.
• If the remainder after dividing $i$ by $3$ is $2$, the $i$-th character is S.
• If the remainder after dividing $i$ by $3$ is $0$, the $i$-th character is A.

The following operations can be performed $0$ or more times on the string.

• Remove one character from the string.
• Add one character at the beginning of the string.
• Add one character at the end of the string.

By performing operations on the given string $X$, we try to change $X$ into a string of the same length as $X$, which the KSAAC staff like. Find the minimum number of operations required for it.

Input

The first line contains a string $X$.

Output

Print the minimum number of operations needed to change the given string $X$ into a string of the same length as $X$, which the KSAAC staff like.

Constraints

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

Scoring

Examples

Input 1

KKSKASKA

Output 1

8