Diversity

Alice is interested in diverse numbers. She defines a diverse number as an integer that contains no consecutive repeated digits. For example, the numbers $1311$ and $333$, are not diverse, as the first contains consecutive $1$s, and the second contains consecutive $3$s. Examples of diverse numbers include $1312$, $340$ and $12345$.

Given an integer $N$, help Alice find the smallest diverse number that is not less than $N$.

Input

There will be a single line containing the integer $N$ ($1 \le N \le 2\,000\,000\,000$).

Output

You should print a single integer – the smallest diverse number that is not less than $N$.

Subtasks

• Subtask 1 (20%): $N \le 100\,000$
• Subtask 2 (30%): All digits of $N$ are the same
• Subtask 3 (50%): No further restrictions apply