Xóa chữ số

Cho một số nguyên dương \(n\).
Ở mỗi bước, bạn có thể trừ \(n\) đi một số nguyên là một trong các chữ số (khác \(0\)) của \(n\).

Hãy tìm số bước nhỏ nhất cần thực hiện để đưa \(n\) về \(0\).

Input

Một dòng duy nhất chứa số nguyên \(n\) (\(1 \le n \le 10^6\)).

Output

In ra một số nguyên — số bước ít nhất cần thiết để đưa \(n\) về \(0\).

Notes

Với \(n = 27\), đáp án là \(5\). Một cách tối ưu là:
\(27 \rightarrow 20 \rightarrow 18 \rightarrow 10 \rightarrow 9 \rightarrow 0\).