A - At most twice

Time limit: 3 s
Memory limit: 256 MiB
Languages: C, C++, Java, Haskell, ... (details)

Given a positive integer $U$, find the largest integer $L$ such that $L \leq U$ and $L$ does not contain any digit more than twice.

Input

The input consists of a single line that contains an integer $U$ ($1 \leq U \leq 10^{18}$).

Output

Output a line with an integer representing the largest number less than or equal to $U$ that does not contain any digit more than twice.

Sample test(s)

Input
2210102960
Output
2210099887
Input
1000000000000000000
Output
998877665544332211
Input
1001223343
Output
998877665
Input
20152015
Output
20152015