На i-ому місці у послідовності знаходиться найбільше ціле число з i цифр, у якому кожна пара сусідніх цифр різна.
Дано натуральне число k (1 \leq k \leq 100000).
Виведіть k-те число послідовності.
Приклад 1
