题目描述

小紫最近在学习递归，他发现递归是一个神奇而又有趣的算法，递归就像一位魔法师又像一台具有人工智能的机器人一样，只要你给他一些数据，那么他好像会莫名其妙而又神通广大的把答案给你。

当一个问题可以分解成一些子问题，而该子问题又和母问题具有相同的套路解法，只是范围变化了而已，那么这个题的特性就具备递归的特性。

递归虽然很神奇也很简单，但是递归有一个致命缺陷，那就是递归嵌套会占用很多内存开销和消耗计算时间，所以一定要注意数据范围。

小紫发现下面这题其实具备递归的特性，你可以尝试用递归算法来完成任务，但是由于这题的数据范围特别大，所以如果只是简单粗暴的进行计算，显然是会超时的。

现在D老师给你一个数字，然后按照下面要求完成任务：

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

比如对于整数 $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 分）：没有特殊限制。