e-olymp
Задачі

Магический Множитель

Магический Множитель

Эльфийские рассы Средиземья считали, что некоторые числа являются более важными, чем другие. При использовании конкретного количества n металла для выплавки меча, они считают, что меч будет наиболее мощным, если его толщина k выбрана согласно следующему правилу:

Задано неотрицательное целое число n. Найти наименьшее k, для которого десятичное представление чисел в последовательности

n, 2n, 3n, 4n, 5n, ..., kn

содержит все десять цифр (от 0 до 9) как минимум один раз?

Лорд Элронд из Ривенделл поручил Вам разработать алгоритм, который найдет оптимальную толщину k для любого заданного количества металла n.

Входные данные

Каждая строка содержит одно число n (1n200000000).

Выходные данные

Для каждого теста вывести в отдельной строке требуемое значение k - такое что каждая цифра от 0 до 9 встречается хотя бы один раз.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
1
10
123456789
3141592
Вихідні дані #1
10
9
3
5
Джерело 2012 ACM North America - Pacific Northwest, November 3, Problem B