题目链接:http://codeforces.com/problemset/problem/1060/B
Time limit per test: 2 seconds Memory limit per test: 512 megabytes

Problem Description

You are given a positive integer n.
Let S(x) be sum of digits in base 10 representation of xx, for example, S(123)=1+2+3=6, S(0)=0.
Your task is to find two integers a,ba,b, such that 0≤a,b≤n, a+b=n and S(a)+S(b) is the largest possible among all such pairs.

Input

The only line of input contains an integer n (1≤n≤10^12)

Output

Print largest S(a)+S(b) among all pairs of integers a,b, such that 0≤a,b≤n and a+b=n.

Input

35
10000000000

Output

17
91

Note

In the first example, you can choose, for example, a=17 and b=18, so that S(17)+S(18)=1+7+1+8=17. It can be shown that it is impossible to get a larger answer.

In the second test example, you can choose, for example, a=5000000001 and b=4999999999, with S(5000000001)+S(4999999999)=91. It can be shown that it is impossible to get a larger answer.

Solving Ideas

将n分离成最高项和其余项两项，然后把最高项的减一，另一项加一，使其出现最多的9。
例如:
n=359=300+59=299+60, 则s(299)+s(60)=2+(3-1)*9+6+0=26;
其中(3-1)指的是最高位后有多少个9.
n=99=90+9=89+10, 则s(89)+s(10)=8+(2-1)*9+1+0=18;
n=2568=2000+568=1999+569, 则s(1999)+s(569)=1+(4-1)*9+5+6+9=48。
具体见代码:

#include <bits/stdc++.h>
using namespace std;
int main(){
    char s[15];
    int ans, len, c, t;
    scanf("%d", &t);
    while (t--) {
        c = 1;
        ans = 0;
        scanf("%s", s);
        len = strlen(s);
        ans += s[0] - '0' + (len - 1) * 9 - 1;
        for (int i = len - 1; i > 0; i--) {
            s[i] += c;
            c = (s[i] - '0') / 10;
            s[i] = (s[i] - '0') % 10 + '0';
            ans += s[i] - '0';
        }
        printf("%d\n", ans + c);
    }
    return 0;
}