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.

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

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.

Input

2210102960

Output

2210099887

Input

1000000000000000000

Output

998877665544332211

Input

1001223343

Output

998877665

Input

20152015

Output

20152015