P10571 [JRKSJ R8] Three Times Seven Is Twenty-One

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.

One line containing a digit string $s$.

One line containing an integer representing the answer.

### 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|$. | $\text{Subtask}$ | $n\le $ | Score | | :----------: | :----------: | :----------: | | $1$ | $4$ | $10$ | | $2$ | $8$ | $10$ | | $3$ | $17$ | $20$ | | $4$ | $10^3$ | $20$ | | $5$ | $10^6$ | $40$ | For $100\%$ of the testdata, $1\le n\le 10^6$, and $s$ consists of digits from $1\sim 9$. Translated by ChatGPT 5