Colorful baloons

There are n red and blue balloons along the rope from left to right. These balloons are represented by a string s of n characters.

If the i-th character of s is 0, the i-th balloon from the left is colored red, if it is 1, it is colored blue.

You have to recolor some of these balloons so that there are no neighboring balloons of the same color. What is the least number of balloons to be repainted?

Input data

One string s (1 ≤ |s| ≤ 10^5) representing the colors of balloons. Let |s| be the length of the string s.

Output

Print the minimum number of balloons that need to be repainted in order to satisfy the given condition.

Examples

Note

In the first test, the condition of the problem can be fulfilled by painting the middle (second) ball with blue color.

In the second test, there is no need to repaint the balloons.