Huy đang xem xét tập hợp các số đẹp, theo quan điểm của Huy thì các số có giá trị là ~2^k~ hoặc ~-2^k~ là những số đẹp, với ~k~ là các số nguyên dương. Với bất kì một số tự nhiên nào ta cũng có thể biểu diễn nó dưới dạng tổng của một dãy các số đẹp khác nhau.
Với số ~n = 109~ ta có thể biểu diễn nó thành tổng của các số đẹp là ~2^7 + (-2^4) + (-2^2) + 2^0~.

Yêu cầu

Cho số ~n~ hãy tìm cách biểu diễn ~n~ thành tổng của các số đẹp sao cho số lượng số đẹp cần dùng là ít nhất có thể.

Dữ liệu

Một dòng duy nhất gồm một xâu nhị phân duy nhất là biểu diễn của số ~n~ trong hệ nhị phân.

Kết quả

Đưa ra một số duy nhất là số lượng số đẹp ít nhất cần dùng để biểu diễn số ~n~.

Input

1101101

Output

4