Problem Description

You are given a string \( s \) consisting of digits from \( 1 \) to \( 9 \). The number represented by the string \( s \) is obtained by interpreting it as a decimal number. Formally, a string \( s \) of length \( n \) represents the number \(\sum_{i=1}^n 10^{n-i}s_i\).

You can perform several operations on this string. In each operation, you can choose a position \( 1 \le p \le n \) and modify \( s_p \) to any digit from \( 1 \) to \( 9 \). Your task is to ensure that the string does not contain any non-empty substring whose represented number is a power of \( 2 \) (i.e., \( 2^k \) where \( k \in \mathbb{N} \)). You need to find the minimum number of operations required.

Input Format

A single line containing the string \( s \).

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

2468

Sample Output #1

3

Sample Input #2

164

Sample Output #2

2

Sample Input #3

65535

Sample Output #3

0

Notes

Sample Explanation

For Sample #1, the non-empty substrings of \( s \) that represent numbers which are 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 \) that represent numbers which are powers of \( 2 \) are \( 1, 4, 16, 64 \). Changing \( s \) to \( 666 \) is one of the optimal solutions.

Data Size and Constraints

This problem uses subtask testing.

Let \( n = |s| \).

For \( 100\% \) of the data, \( 1 \le n \le 10^6 \), and \( s \) consists of digits from \( 1 \) to \( 9 \).

见题面 Input 部分

见题面 Output 部分