Định nghĩa \(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 một số nguyên \(2 \le k \le 100000\).

Output

• In ra giá trị \(f(x)\) nhỏ nhất.

Sample Test

6

3