Problem Statement

Ao loves certain sets of non-negative integers.

Let $X$ be a set of non-negative integers. Whether she loves $X$ or not is determined as follows:

• If $X$ is the empty set, she loves $X$.
• If, for any (possibly the same) two elements $u$ and $v$ in $X$, at least one of $u+v$ and ${\\rm abs}(u-v)$ is contained in $X$, she loves $X$.
• If none of the above conditions is satisfied, she does not love $X$.

You are a big fan of Ao, and going to present her a set of non-negative integers. Currently you have a set $A$ of non-negative integers. You want to erase (possibly zero) elements from $A$ so that she loves the set of remaining integers. You also want to maximize the number of remaining integers. What is the largest number of remaining integers?

Constraints

• $A$ is not empty.
• The largest element in $A$ is not larger than $500,000$

Input

Input is given from Standard Input in the following format:

$S$

Here, $S=S_0S_1...S_{|S|-1}$ is the string which indicates $A$. For each $i$ ( $0 \\leq i \\leq |S|-1$ ), $S_i =$ 1 if $A$ contains $i$ and $S_i =$ 0 if not. It is guaranteed that $S_{|S|-1}$ is 1.

Output

Print the largest number of remaining integers.

Sample Input 1

1000001001011

Sample Output 1

3

The set $A = \\{0,6,9,11,12\\}$. If you erase $9$ and $11$, Ao loves the set of remaining integers: $\\{0,6,12\\}$.

Sample Input 2

10110110101

Sample Output 2

4

Sample Input 3

0111

Sample Output 3

0

The set of remaining integers must be empty.