Different numbers

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

Input

The input consists of a single integer n (1 ≤ n ≤ 10^18).

Output

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

Examples