Square Digital Root

For a given natural number N, we define the concept of a square digital root. Begin by writing an infinite sequence of numbers where the first number is N. Each subsequent number in the sequence is calculated as the sum of the squares of the digits of the previous number in the sequence. The square digital root is the smallest number that appears in this sequence.

Write a program to find the square digital root for a given number.

Input

The input consists of a single line containing a natural number N, which does not exceed 10^1000000.

Output

Output the square digital root of the number N on a single line.

Examples