Sinan loves to read strange things. Lately, to show that he is very good at computers (and to prevent people in the subway from understanding what he reads) he started reading texts written with only 0 and 1's. He is happy with this situation but his sanity is slowly fading.

Sinan wrote a note on Aslı's notebook. Aslı wants to erase that note because that note is just a bunch of meaningless 0's and 1's.

Aslı has a special eraser. This eraser can only erase strings which has a first character different than the rest of the string, or it can erase a single character. If it erases a string from the middle of the text, the text can be considered as a single string. How many erase-moves does Aslı need to erase the note written on her notebook?

Input

The note of Sinan: \(\mathbf{S}\)

Output

The minimal number of operations needed to erase the note.

Constraints

• \(1 ≤ |S| ≤ 10000\)
• Each character of the Sinan's note is either 0 or 1.

Example

Input:

11000110

Output:

3

Notes

For this example input, one optimal sequence of operations is:

• Erase the "011" part, the current string becomes "11000",
• Erase the "1000" part, the current string becomes "1",
• Erase the "1" part, Aslı's notebook is clean now.