Yermolai and the Keyboard

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Yermolai and his friends are fond of various chemical substances. So much so, that they send each other substance formulas via SMS. Yermolai’s trouble is that he is very impatient. To make matters worse, he is out of luck with his phone.

There are only lowercase Latin letters and a Shift key on the phone’s keyboard. If you press Shift once, the next letter will be uppercase, and all letters after that will be lowercase again. If you press Shift twice, all subsequent letters will be uppercase until Shift is pressed once again.

The phone takes exactly one second to process each key press, so Yermolai has learned to use the Shift key optimally.

Can you calculate the minimum amount of time Yermolai needs to spend to type a message?

Input

The first and only line contains the text \(t\) that Yermolai wants to type.

Output

In a single line, output a single integer — the minimum number of seconds needed to type the message.

Constraints

The text \(t\) consists only of lowercase and uppercase letters of the Latin alphabet,

\(1 \le |t| \le 10^5\).

Samples