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, selecting one of the two each time:

• Remove two adjacent characters from the string.
• Add two identical characters to the beginning of the string.

By performing appropriate operations on the given string $X$, we want to change $X$ into a string that the KSAAC staff like with the same length as $X$. Find the minimum number of operations required.

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 that the KSAAC staff like with the same length as $X$.

It is guaranteed that by performing the given operations a finite number of times, the given string $X$ can be changed into a string that the KSAAC staff like with the same length as $X$.

Constraints

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

Scoring

Examples

Input 1

KSKA

Output 1

8

Input 2

KKK

Output 2

6

Note

In Example 1, the goal is to change the given string to KSAK.

Adding KK, SS, AA, KK makes the string KKSSAAKKKSKA. Deleting the $2$nd, $6$th, $9$th, and $11$th characters, along with the characters to their right, yields the KSAK.

In Example 2, the goal is to change the given string to KSA.

Adding KK, SS, AA makes the string KKSSAAKKK. Deleting the $2$nd, $6$th, and $8$th characters, along with the characters to their right, yields the KSA.