Problem Description

You are given a digit string $s$ consisting of digits from $1\sim 9$. Define the number represented by a digit string $s$ as the decimal value obtained by treating it as a base-10 number. Formally, for a digit string $s$ of length $n$, the represented number is $\sum_{i=1}^n 10^{n-i}s_i$.

You may perform several operations on this digit string. In each operation, you can choose a position $1\le p\le n$ and change $s_p$ to any digit from $1\sim 9$. You need to make sure that this digit string has no non-empty substring whose represented number is $2^k(k\in \N)$, i.e., any non-negative integer power of $2$. Please find the minimum number of operations.

Input Format

One line containing a digit string $s$.

Output Format

One line containing an integer representing the answer.

2468

3

164

2

65535

0

Hint

Sample Explanation

For sample $1$, the non-empty substrings of $s$ whose represented numbers are non-negative integer powers of $2$ are $2,4,8$. Changing $s$ to $5963$ is one of the optimal solutions.

For sample $2$, the non-empty substrings of $s$ whose represented numbers are non-negative integer powers of $2$ are $1,4,16,64$. Changing $s$ to $666$ is one of the optimal solutions.

Constraints

This problem uses bundled testdata.

Let $n=|s|$.

For $100\%$ of the testdata, $1\le n\le 10^6$, and $s$ consists of digits from $1\sim 9$.

Translated by ChatGPT 5