题目描述

给你一个由 $1\sim 9$ 的数字组成的数字串 $s$。定义一个数字串 $s$ 表示的数为将其看作十进制数得到的数。形式化地说，长为 $n$ 的数字串 $s$ 表示的数是 $\sum_{i=1}^n 10^{n-i}s_i$。

你可以对这个数字串执行若干次操作，每次操作中你可以选定一个位置 $1\le p\le n$ 并将 $s_p$ 修改为任意 $1\sim 9$ 中的数字。你需要使该数字串不存在任何一个非空子串满足这个子串表示的数字是 $2^k(k\in \N)$ 即 $2$ 的任意非负整数次幂，请你求出最少的操作次数。

输入格式

一行一个数字串 $s$。

输出格式

一行一个整数表示答案。

2468

3

164

2

65535

0

提示

样例解释

对于样例 $1$，满足表示的数是 $2$ 的非负整数次幂的 $s$ 的非空子串有 $2,4,8$，将 $s$ 修改为 $5963$ 是最优解之一。

对于样例 $2$，满足表示的数是 $2$ 的非负整数次幂的 $s$ 的非空子串有 $1,4,16,64$，将 $s$ 修改为 $666$ 是最优解之一。

数据规模与约定

本题采用捆绑测试。

令 $n=|s|$。

对于 $100\%$ 的数据，$1\le n\le 10^6$，$s$ 由 $1\sim 9$ 的数字组成。