Project Euler #56: Powerful digit sum

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

A googol is a massive number: one followed by one-hundred zeros. is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, , where , what is the maximum digital sum?

Input Format

Input contains an integer

Constraints

Output Format

Print the answer corresponding to the test case.

Sample Input

Sample Output

Explanation

and , which is the maximum digital sum for this range.