题目描述

Ao 喜欢某些非负整数的集合。

令 $X$ 为非负整数的集合。判断她是否喜欢 $X$ 的规则如下：

• 如果 $X$ 是空集，她喜欢 $X$。
• 如果对于 $X$ 中的任意两个元素 $u$ 和 $v$（可能相同），$u+v$ 和 ${\\rm abs}(u-v)$ 中至少有一个属于 $X$，她喜欢 $X$。
• 如果以上两个条件都不满足，则她不喜欢 $X$。

你是 Ao 的铁杆粉丝，打算给她一个非负整数的集合作为礼物。目前你手上有一个集合 $A$，你想要从 $A$ 中擦除（可以是零个）元素，使得 Ao 喜欢剩下的整数集合，并且你希望剩下的整数数量最大化。那么剩下的整数最多有多少个？

约束条件

• $A$ 集合不为空
• $A$ 中最大的元素不超过 $500,000$

输入

输入通过标准输入给出，格式如下：

$S$

这里，$S=S_0S_1...S_{|S|-1}$ 表示集合 $A$。对于每个 $i$ （$0 \leq i \leq |S|-1$），$S_i =$ 1 表示 $A$ 包含 $i$，$S_i =$ 0 表示 $A$ 不包含 $i$。保证 $S_{|S|-1}$ 是 1。

输出

输出剩下的整数的最大数量。

样例输入 1

1000001001011

样例输出 1

3

集合 $A = \\{0,6,9,11,12\\}$。如果擦除 $9$ 和 $11$，Ao 就会喜欢剩下的整数集合：$\\{0,6,12\\}$。

样例输入 2

10110110101

样例输出 2

4

样例输入 3

0111

样例输出 3

0

剩下的整数集合必须为空集。