Задача 13. Формула наших времён ≡

Условие

...

И цифры соединятся,

И пальцы

Вопьются в ладонь...

На что ни разделишь 13 —

Получится дробь...

И огонь!

Михаил Светлов, "Тринадцать", 1930 г.

Хорошо этим поэтам! Срифмовал себе пару строк, добавил пафоса и восклицательных знаков — глядишь, уже и в "Литературной газете" напечатали, и в МАССОЛИТ приняли, и в "Грибоедов" пускают. Удобно пристроился Амвросий! А если ты математик и всю жизнь разрабатываешь теорию чисел? Напечатают твою формулу на первой странице "Известий"? Ага, жди, Фока... Так и проживёшь всю жизнь в крохотной комнатке с общей кухней под укоризненным взглядом жены.

Ну, хоть небольшую задачку про бесконечные периодические дроби удалось в "Математический вестник" пристроить, главный редактор к тринадцатой годовщине Октября собирал всё, что связано с этим числом. Через недельку денежку в кассе выдадут, можно будет и в Торгсин супругу сводить, и в Варьете...

Определите наименьшее натуральное число, при делении которого на 13 в записи цифр результата встретится число n. На десятичный разделитель (если он образуется) не обращайте внимания.

Для определённости считайте, что если число делится на 13 нацело, то дробной части не образуется.

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁹

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

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

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

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

В первом примере дано n = 1930.

25113 = [19.30]76...

Во втором примере дано n = 61.

213 = 0.15384[61]53...

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

1930

251

61

2