ABC

Time limit1sMemory limit128 MB

Summary

Build a string of A, B, and C where each second inserts one of A, B, C, or the block ABC at any position; find the minimum number of insertions.

Level: Medium7 of 10
Topics: Dynamic programming, String, Intervals, Implementation
Solved: No attempts yet

Problem

After 25 years of effort, Taesu has learned the letters A, B, and C. Having achieved the greatest feat of his life, Taesu made a game to commemorate it. The game starts from an empty string and builds a string S consisting only of A, B, and C. In one second, Taesu can perform one of the following operations.

Insert A at any position in the string.
Insert B at any position in the string.
Insert C at any position in the string.
Insert ABC at any position in the string.

Find the minimum time Taesu needs to build the string S, and help him finish the game faster!

Input

The first line gives the string S consisting of A, B, and C. (1 ≤ |S| ≤ 500)

Output

Print the minimum time needed to build the string S.

Examples2

Example 1
Input
```
AABBCC
```
Expected output
```
4
```
Example 2
Input
```
ABABCC
```
Expected output
```
2
```