Background

小铭成功搭建好法坛后发现他仍不能升天，他意识到了自己的法力还不足够升天，于是他便去找大法师安东尼达斯。。。

Description

大法师对小铭说：“你需要我的帮助。不过你得帮我解开这个谜题，我才能帮你升天。”。
小铭拿到一道谜题，在10进制下，求\(K\)的倍数中，每一位上的数字和的最小值。

Format

Input

一个整数\(K\)。

Output

输出一个整数。

Sample 1

Input1

6

Output1

3

解释：6的倍数中，12满足条件，每个位上的数和的和为\(1+2 = 3\)

Input2

41

Output2

5

解释：41的倍数中，\(41 \times 271 = 11111\)满足条件，每个位上的数和的和为 5

Limitation

Time limit : 1sec / Memory limit : 256MB
本题共有100个测试点，数据有梯度。
对于\(100\%\)的数据，\(K \le 10^5\)