Задача D. Плавно-оригинальные числа

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Назовем число плавным, если его две соседние цифры различаются не более, чем на 1. Например, числа 7, 1011, 2345 или 2323455665 - плавные, а 13, 90 или 102 - нет.

Назовем число оригинальным, если оно обладает следующим свойством: первые k цифр этого числа образуют число, делящееся на k для любого 1 ≤ k ≤ длина числа. Например, число 3216 - оригинальное. Действительно: 3 делится на 1, 32 делится на 2, 321 делится на 3, 3216 делится на 4.

Найдите n-е по счету число, которое одновременно является и плавным, и оригинальным.

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

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

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

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

Ограничения

1 ≤ n ≤ 60

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

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

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

Стандартный вход Стандартный выход
1
1
1
2
10
10

0.245s 0.010s 15