Given a string consisting of numbers 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 numbers 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