Square Digital Root#1675
For a given natural number , we define the concept of a square digital root. Construct an infinite sequence where the first number is , and each subsequent number in the sequence is the sum of the squares of the digits of the previous number. The square digital root is the smallest number that appears in this sequence.
Write a program to determine the square digital root for the given number.
The input consists of a single line containing a natural number , which does not exceed 10^{1000000}.
Output the square digital root of the number on a single line.
Example 1