Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

C. George and Number

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGeorge is a cat, so he really likes to play. Most of all he likes to play with his array of positive integers *b*. During the game, George modifies the array by using special changes. Let's mark George's current array as *b*_{1}, *b*_{2}, ..., *b*_{|b|} (record |*b*| denotes the current length of the array). Then one change is a sequence of actions:

- Choose two distinct indexes
*i*and*j*(1 ≤*i*,*j*≤ |*b*|;*i*≠*j*), such that*b*_{i}≥*b*_{j}. - Get number
*v*=*concat*(*b*_{i},*b*_{j}), where*concat*(*x*,*y*) is a number obtained by adding number*y*to the end of the decimal record of number*x*. For example,*concat*(500, 10) = 50010,*concat*(2, 2) = 22. - Add number
*v*to the end of the array. The length of the array will increase by one. - Remove from the array numbers with indexes
*i*and*j*. The length of the array will decrease by two, and elements of the array will become re-numbered from 1 to current length of the array.

George played for a long time with his array *b* and received from array *b* an array consisting of exactly one number *p*. Now George wants to know: what is the maximum number of elements array *b* could contain originally? Help him find this number. Note that originally the array could contain only positive integers.

Input

The first line of the input contains a single integer *p* (1 ≤ *p* < 10^{100000}). It is guaranteed that number *p* doesn't contain any leading zeroes.

Output

Print an integer — the maximum number of elements array *b* could contain originally.

Examples

Input

9555

Output

4

Input

10000000005

Output

2

Input

800101

Output

3

Input

45

Output

1

Input

1000000000000001223300003342220044555

Output

17

Input

19992000

Output

1

Input

310200

Output

2

Note

Let's consider the test examples:

- Originally array
*b*can be equal to {5, 9, 5, 5}. The sequence of George's changes could have been: {5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}. - Originally array
*b*could be equal to {1000000000, 5}. Please note that the array*b*cannot contain zeros. - Originally array
*b*could be equal to {800, 10, 1}. - Originally array
*b*could be equal to {45}. It cannot be equal to {4, 5}, because George can get only array {54} from this array in one operation.

Note that the numbers can be very large.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:35:51 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|