Project Euler #65: Convergents of e

_{This problem is a programming version of Problem 65 from projecteuler.net}

The square root of 2 can be written as an infinite continued fraction.

The infinite continued fraction can be written,

indicates that 2 repeats ad infinitum. In a similar way,

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for .

Hence the sequence of the first ten convergents for are:

What is most surprising is that the important mathematical constant,

The first ten terms in the sequence of convergents for are:

The sum of digits in the numerator of the convergent is .

Find the sum of digits in the numerator of the convergent of the continued fraction for .

Input Format

Input contains an integer

Constraints

Output Format

Print the answer corresponding to the test case.

Sample Input

Sample Output