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

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

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

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

В единственной строке задается натуральное число N, не превышающее 10^1000000.

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

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

Примеры