Given a string consisting of digits from '0' to '9', find the smallest non-negative integer that does not occur as a contiguous subsequence in the given string.

Input

Input only contains a string S (|S| ≤ 100000), which consists of digits from '0' to '9'.

Output

Output the smallest non-negative integer that does not occur as a contiguous subsequence in the given string.

Example

Input 1
0123456789
Output 1
10

Input 2
21698921085321984125

Output 2
7

Input 3
01234567891011121314151617181920

Output 3
22