YouKnowWho has finally found a way to get paid. He has to find the sum of the digits of the largest integer K such that:

• K ≤ (5000 + n)!
• K has no two equal adjacent digits (e.g., “00”, “11”, “22”, … are not allowed).

Input

Single integer n.

Output

Print the sum of the digits of the largest valid K.

Sample Input

-4996

Sample Output

6

Explanation

For n = -4996, (n + 5000)! = 24. The number 24 satisfies the adjacency rule and is the largest valid K. Therefore, the answer is 2 + 4 = 6.