Дима недавно поступил на работу в научно-исследовательский институт «Числовые Последовательности». Как следует из названия этого института, основным направлением его работы является проведение различных исследований в области числовых последовательностей. Недавно руководитель отдела, где начал работать Дима, при решении одной из проблем столкнулся с весьма интересной последовательностью чисел a1, a2, …, an, …, которая определяется следующим образом: следующим образом: a1 = 0 и каждое последующее число ai (1 < i ≤ n) определяется как наименьшее большее натуральное число, десятичная запись которого не содержит цифр, представленных в десятичной записи ai-1.
Требуется написать программу, которая по значению числа n вычисляет величину an.
Формат входных данных
Входной файл содержит целое число n (1 ≤ n ≤ 500).
Формат выходных данных
В выходной файл необходимо вывести ответ на задачу.
Примеры входных и выходных файлов
| входные данные |
выходные данные |
| 1 |
0 |
| 28 |
911 |