G. Life is Too Short
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a binary string $$$S$$$ consisting only of characters $$$0$$$ and $$$1$$$.

Your task is to determine the minimum possible length of a binary string (composed of $$$0$$$ and $$$1$$$) that is not a subsequence of S.

†A string $$$Q$$$ is called a subsequence of string $$$P$$$ if $$$Q$$$ can be obtained from $$$P$$$ by deleting some (possibly, zero or all) characters without changing the order of the remaining characters. For example, subsequences of $$$1011101$$$ are $$$0$$$, $$$1$$$, $$$11111$$$, $$$0111$$$, but not $$$000$$$, nor $$$11100$$$.

Input

A single line containing the binary string $$$S (1 \leq |S| \leq 10^6)$$$.

Output

Output a single integer — the minimum length of a binary string that is not a subsequence of $$$S$$$.

Examples
Input
0110
Output
3
Input
1000
Output
2
Note

In the first example, all binary strings of length $$$1$$$ and $$$2$$$ are present as subsequences. But $$$3$$$ length strings like $$$000$$$, $$$101$$$ etc. are not present. So the answer is $$$3$$$.

In the second example, all binary strings of length $$$1$$$ and $$$2$$$ are present as subsequences, except $$$01$$$, $$$11$$$. So the answer is 2.