Ta định nghĩa hàm f(x) là tổng các chữ số của số nguyên x. Cho số nguyên K, hãy tìm giá trị f(x) nhỏ nhất có thể khi xét các số nguyên dương x chia hết cho K.

Input:

• Gồm số nguyên K (2 ≤ K ≤ 100000).

Output:

• In ra giá trị f(x) nhỏ nhất cần tìm

Sample Input

4

Sample Output

1

Sample Input

6

Sample Output

3

Giải thích

• Ở ví dụ thứ nhất, trong số các giá trị x chia hết cho 4, ta có thể chọn x = 1000. Khi đó, f(x) = 1 + 0 + 0 + 0 = 1

• Ở ví dụ thứ hai, trong số các giá trị x chia hết cho 6, ta có thể chọn x = 12. Khi đó, f(x) = 1 + 2 = 3