You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Csvoner 最近学习了数位和，他学会了用下面的代码计算 $x$ 的数位和 $num$：

num = 0;
while (x > 0)
{
    num += x % 10;
    x /= 10;
}

Csvoner 觉得只算数位和没有意思，想到一个算出一位数位和的方法：

• 他想可以先把一个数算出数位和，得到一个新造的数
• 然后把新数继续求数位和，以此类推
• 直到最终得到一个一位数，就以此为一位数位和

比如对于整数 $19970111$，可以算出数位和 $1+9+9+7+0+1+1+1=29$，继续算出数位和 $2+9=11$，最终就能得到 $19970111$ 的一位数位和 $1+1=2$.

现在给你整数 $n$，请你求出 $1\sim n$ 之间的所有整数对应的一位数位和，然后算出这些一位数位和之和。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示 $n$ 个一位数位和之和。

5

15

15

66

19970111

99850548

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10^{12}$。

• 子任务 1（30 分）：$1\le n\le 9$。
• 子任务 2（30 分）：$1\le n\le 10^6$。
• 子任务 3（40 分）：没有特殊限制。