问题描述

定义一个正整数的数位和为这个数字十进制表示下各位数字之和，如 1926 的数位和是 18，19260 的数位和是 18，192608 的数位和是 26。

请找出一个满足模 K 等于 0 的正整数，使得数位和最小，输出最小的数位和。

Input

一个数K 。

Output

一个数表示最小数位和。

Examples

输入样例1:

6

输出样例1:

3

输入样例2:

41

输出样例2:

5

输入样例3:

79992

输出样例3:

36

Notes

前 50%的测试数据满足1 ≤ K ≤ 10;

全部测试数据满足1 ≤ K ≤ 10^5 。