Different numbers#8263

Different numbers

1 second
64 megabytes
Hard

Senya is fond of numbers where no two consecutive digits are the same. Given an integer , your task is to help Senya find the smallest integer that is strictly greater than and meets his preference.

Input

The input consists of a single integer (1 \le n \le 10^{18}).

Output

Print the smallest integer greater than that does not contain any consecutive identical digits.

Examples

Example 1

Loading
Loading