Contest Duration: - (local time) (300 minutes) Back to Home
E - Self-contained /

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.