Квадратний цифровой корінь

Для заданого натурального числа N визначимо поняття квадратного цифрового кореня. Запишемо нескінченну послідовність чисел, у якій перше число рівне N, а кожне чергове число дорівнює сумі квадратів цифр у десятковому поданні попереднього числа послідовності. Квадратним цифровим коренем буде найменше число, яке зустрінеться у цій послідовності.

Напишіть програму, яка для заданого числа визначає його квадратний цифровий корінь.

Вхідні дані

У єдиному рядку задано натуральне число N, яке не перевищує 10^1000000.

Вихідні дані

У єдиному рядку виведіть квадратний цифровий корінь числа N.

Приклади