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

Для произвольного числа цифровой корень определяется следующим образом:

1. Если сумма цифр числа меньше десяти, то цифровой корень и есть сумма цифр этого числа.
2. В противным случае цифровой корень числа равен цифровому корню суммы его цифр.

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

Единственное число n (0 ≤ n ≤ 231- 1).

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

Вывести цифровой корень числа n.