Avoiding Powers of Two Substrings

You are given a string s consisting of digits from 1 to 9. The number represented by s is defined in the usual way as a decimal number:

\(\displaystyle Number(s)=\sum_{i=1}^{n}10^{n-i}\,s_i\)

You are allowed to perform several operations. In each operation, you can choose any position \(1\le p\le n\) and change the digit \(s_p\) to any digit from 1 to 9. Your goal is to modify s so that there is no non-empty contiguous substring of s whose numeric value is equal to \(2^k\) for some non-negative integer \(k\). Formally, there should be no substring s[l...r] such that \[ \sum_{i=l}^{r}10^{r-i}\,s_i = 2^k\quad (k\in \mathbb{N}). \]

Compute the minimum number of operations required.

inputFormat

The input consists of a single line containing the string s (digits 1-9 only).

outputFormat

Output a single integer, representing the minimum number of operations required.

sample

16

1