Кристалл цифровой силы

В одной игре у героя есть «кристалл силы» с числом X. После каждого боя кристалл «сжимает» число: заменяет его на сумму его цифр. Если получившееся число всё ещё двузначное или больше — сжатие повторяется, пока не останется ровно одна цифра.

Твоя задача — узнать, какая цифра останется в кристалле.

Важно: X может быть до 10^18, то есть больше 32-битного типа (как на олимпиадах). В Python это не проблема.

Формат ввода

Одно целое число X.

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

Одну цифру — итоговое число в кристалле после всех сжатий.

Ограничения

• 0 ≤ X ≤ 10^18

Пример

Ввод:

987654

Вывод:

3

Ключевое наблюдение: сколько бы раз ты ни заменял число на сумму его цифр, итоговая одна цифра называется цифровой корень. Он почти всегда равен остатку числа по 9 — потому что число и сумма его цифр дают один и тот же остаток при делении на 9 (из-за того, что 10 ≡ 1 (mod 9), значит 10^k ≡ 1).

Почему это работает здесь: вместо многократных «сжатий» (которые выглядят как цикл) можно сразу получить ответ за O(1), даже если X до 10^18.

План решения:

• Считай X.
• Если X == 0, ответ 0 (важный отдельный случай).
• Иначе посчитай r = X % 9.
• Если r == 0, то цифровой корень равен 9 (это все числа кратные 9: 9, 18, 27, ...).
• Иначе ответ равен r.

Мини-сниппет формулы:

• r = x % 9
• ans = 9 if r == 0 else r (но только когда x != 0)

Сложность: по времени O(1), по памяти O(1).

Частая ошибка: забыть про X = 0. Для нуля цифровой корень не 9, а 0, поэтому проверка x == 0 должна быть раньше правила про x % 9 == 0.