Different digits

Interview

Time limit1sMemory limit512 MB

Summary

Given n up to 10^18, find the smallest integer strictly greater than n whose decimal digits have no two adjacent equal digits.

Level: Medium5 of 10
Topics: Greedy, Math, Implementation, String
Solved: No attempts yet

Problem

Senya likes integers that do not contain two consecutive equal digits. You are given an integer $n$ . Find the smallest integer he likes that is strictly greater than $n$ .

Input

The input contains an integer $n$ ( $1 \le n \le 10^{18}$ ).

Output

Print the smallest integer strictly greater than $n$ that does not contain any two consecutive equal digits.

Examples1

Example 1
Input
```
98
```
Expected output
```
101
```