Time Limit: 3 sec / Memory Limit: 1024 MB

Score : `100` points

### 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.