Có \(N\) viên gạch được sắp xếp thành một hàng từ trái sang phải. Màu ban đầu của mỗi viên gạch được biểu diễn bởi một chuỗi \(S\) có độ dài \(N\).

Viên gạch thứ \(i\) từ bên trái được sơn màu đen nếu ký tự thứ \(i\) của \(S\) là \(0\), và được sơn màu trắng nếu ký tự đó là \(1\).

Bạn muốn sơn lại một số viên gạch thành màu đen hoặc trắng, sao cho bất kỳ hai viên gạch liền kề nào cũng có màu khác nhau.

Ít nhất bao nhiêu viên gạch cần được sơn lại để thỏa mãn điều kiện này?

Ràng buộc

• \(1 \leq \|S\| \leq 10^5\)
• \(S_i\) là \(0\) hoặc \(1\).

INPUT FORMAT

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

S

OUTPUT FORMAT

In ra số lượng viên gạch ít nhất cần được sơn lại để thỏa mãn điều kiện.

Ví dụ:

Input

000

Output

1

Điều kiện có thể được thỏa mãn bằng cách sơn lại viên gạch ở giữa thành màu trắng.

Input

10010010

Output

3

Giải thích ví dụ:

Trong ví dụ này, sơn lại ba viên gạch tại các vị trí 2, 4 và 6 sẽ thỏa mãn điều kiện.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House