ISPIS

문제

Perica got an antique dot matrix printer that he can be control using his personal computer. While playing with his new old printer he discovered that printer recognizes three types of commands: 

• SET(X) – This command sets character X into main memory. 
• NEXT(X) – This command sets character X into secondary memory. 
• WRITE – This command writes a character on the paper. The character to bi printed is read from the main memory unless previous command was NEXT. In that case, character is read from the secondary memory. 

For example, next 8 commands will write “AABAA” on the paper: 

SET(A), WRITE, WRITE, SET(B), WRITE, SET(A), WRITE, WRITE. 

After a lot of thinking, Perica discovered that he could also do it in 7 commands: 

SET(A), WRITE, WRITE, NEXT(B), WRITE, WRITE, WRITE. 

Given a sequence of characters, write a program that will calculate the minimum number of commands needed to print that sequence. 

Note: First command has to be SET. 

입력

The first line contains the sequence of characters to be printed. The sequence contains upper case english letters and is not longer than 10 000. 

출력

Output one integer, the minimum number of commands needed to print the sequence. 

 

힌트

SET(B), WRITE, NEXT(A), WRITE, WRITE, NEXT(C), WRITE, WRITE, SET(A), WRITE, NEXT(C), WRITE, WRITE. 

NN

3

IOIX

7

BABCBACA

13