Стабилизация последовательности

Пусть x – натуральное число. Обозначим как s(x) – сумму цифр его делителей. Например, s(6) = 1 + 2 + 3 + 6 = 12, s(10) = 1 + 2 + 5 + 1 + 0 = 9.

Рассмотрим теперь последовательность a₁ = x, a₂ = s(x), a₃ = s(s(x)), ... , a_n = s(a_n−1), ... .

Скажем, что эта последовательность стабилизируется, если для некоторого i выполняется равенство a_i = a_i+1 (тогда это свойство верно и для любого j > i).

Задано число x. Необходимо выяснить, стабилизируется ли последовательность a_n, и найти минимальное i, для которого a_i = a_i+1.

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

Входной файл INPUT.TXT содержит натуральное число x (x ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите минимальное искомое число i или -1, если оно превышает 1000. В первом случае выведите также во второй строке первые i членов последовательности a_n через пробел.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]