Sequence of Sum of Squares

You are given a positive integer N. Starting from the number 1, generate a sequence where each subsequent number is the sum of the squares of the digits of the current number.

Formally, if the current number is n with digits \(d_1, d_2, \ldots, d_k\), then the next number is computed as:

\( s = d_1^2 + d_2^2 + \cdots + d_k^2 \)

Your task is to compute the N-th number in this sequence. Note that since the sequence starts with 1 and the sum of the squares of the digits of 1 is always 1, the answer will always be 1. However, you are required to implement the algorithm as described.

inputFormat

The input consists of a single integer N (1 \leq N \leq 10^9), read from standard input.

outputFormat

Output the N-th number in the sequence to standard output.

1

1