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.
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 contains an integer
Print the answer corresponding to the test case.