Задача D. Good bye, 2022! ≡

Условие

Завершающийся год оказался богат на интересные и драматичные события. В честь его окончания попробуйте определить n-е по счету число-палиндром, в записи которого используются только цифры 2 и 0 и встретится подстрока "2022".

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10, получат не менее 25 баллов.

Пояснение к примеру

В примере дано n = 1. Число называется палиндромом, если оно одинаково читается как слева направо, так и справа налево. Например, палиндромами являются числа 0, 77, 1001, 97579, а числа 69 или 1024 — не являются.

Первое подходящее число-палиндром, в котором встречается комбинация цифр "2022" — 22022. Следующим таким числом станет 202202.

Примеры тестов

1

22022