Migrated from Lutece 3149 简单的数学题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

妈的，忍不了，一拳把电脑打爆！上勾拳！下勾拳！左勾拳！右勾拳！扫堂腿！回旋踢！这是 Floyd！这是 Dijkstra！这是 SPFA 能判断负环！这是 Kruskal！这是树哈希！这是差分约束！这是矩阵树定理！这是 prufer 序列！这是两遍 dfs 求树的直径！这是拓扑排序！这是缩点成 DAG！这是 Tarjan 求割点和桥！这是 EK、Dinic、ISAP、HLPP 求网络流！这是最大流最小割定理！这是从来都用不到的 k 短路！这是又臭又长的带花树！彻底疯狂！彻底疯狂！彻底疯狂！彻底疯狂！

为了防止大家写图论写得走火入魔，在这里给大家准备了一道简单的数学题。

定义 $f(x)$ 表示 $x$ 的各位数之和，例如 $f(123)=1+2+3=6，f(10086)=1+8+6=15$。

给定一个正整数 $K$，你想找到 $K$ 的一个倍数 $S$，使 $f(S)$ 最小。由于 $S$ 可能非常大，你只需要输出 $f(S)$ 即可。

Input

一行一个正整数 $K (2\leq K\leq 10^7)$。

Output

输出一个整数 $f(S)$。

Samples

6

3

19

2

Note

第一个样例中 $12=2×6$，$f(12)=3$ 为最小值。

第二个样例中 $1000000001=19×52631579$，$f(1000000001)=2$ 为最小值。

Resources

2024 UESTC ICPC Training for Graph