Given a string of digits, find the smallest nonnegative integer that does not occur in the given string as a subsequence. The length of the string is between 1 and 100000, inclusive.

Input

The input consists of several lines (at most 200), each with a single string S, with between 1 and 10^5 digits.

Output

Print a single line for each string containing the smallest nonnegative integer that does not occur in the given string as a subsequence.

Example

Input
9876543210
21698921085321984125
12345678901

Output
11
7
22