Valera 认为一个数字是美丽的,如果它对于某个整数 k (k ≥ 0) 等于 2k 或 -2k 。最近,数学老师要求 Valera 将数字 n 表示为美丽数字的总和。由于瓦莱拉真的很贪心,他想用尽可能少的漂亮数字来完成任务。
帮助 Valera 找出他需要多少个数字。换句话说,如果将数字 n 分解为漂亮的被加数,则需要找到被加数最少的分解的大小。
输入
第一行包含字符串 s (1 ≤ |s| ≤ 106),即数字 n 的二进制表示形式,不带前导零 (n > 0)。
输出
打印一个整数——总共为 n 的漂亮数字的最小数量。
示例
输入 #1
10
输出 #1
1
输入 #2
111
输出 #2
2
输入 #3
1101101
输出 #3
4
注意
在第一个样本中,n = 2 是一个漂亮的数字。
在第二个样本中,n = 7,Valera 可以将其分解为和 23 + ( - 20)。
在第三个样本中,n = 109 可以分解为四个被加数之和,如下所示:27 + ( - 24) + ( - 22) + 20。