Задача №113649. Загадка Сфинкса
С древних времён ужасный крылатый Сфинкс подстерегает путников у Большого Камня по дороге в священный город Истины, задаёт им хитроумные загадки и съедает тех, кто не сумел дать правильный ответ. Турист Пётр тоже решил посетить город Истины и встретил чудовище.
Сфинкс задал ему такую загадку: «На Большом Камне написано число n . Найди наименьшее целое положительное число k , такое что сумма цифр числа k в десятичной системе счисления делится на n и сумма цифр числа k + 1 в десятичной системе счисления делится на n ».
Пётр догадался, что коварный Сфинкс задаёт всем путникам одну и ту же задачу, изменяя лишь число n , и загорелся желанием избавить мир от смертоносных загадок чудовища. Он решил написать на Большом Камне алгоритм, который позволит всем путникам давать правильный ответ на загадку. Помогите ему в этом.
В единственной строке находится целое число n ( 1 ≤ n ≤ 100 000 ).
В случае если искомого числа k не существует, выведите одно число 0 .
В противном случае выведите целое положительное число k , являющееся ответом на загадку Сфинкса. Ответ не должен содержать пробелов и ведущих нулей.
В первом примере суммы цифр чисел k и k + 1 должны делиться на 1. Это условие выполнено для любого целого положительного k , поэтому ответом является 1.
Во втором примере суммы цифр чисел k и k + 1 должны делиться на 4. Числа 39 и 40 удовлетворяют этому требованию, поскольку 3 + 9 = 12 и 4 + 0 = 4 . Нетрудно убедиться, что никакое меньшее число k не является ответом на эту загадку Сфинкса.
1
1
4
39