Lịch Julya vĩ đại

Cho một số nguyên không âm $n$. Mỗi bước, bạn được phép chọn một chữ số $d$ xuất hiện trong biểu diễn thập phân hiện tại của $n$, rồi thay $n$ bởi $n-d$. Lặp lại thao tác này cho đến khi $n$ bằng $0$.

Các dãy trừ khác nhau có thể cho số bước khác nhau. Hãy tìm số bước ít nhất để đưa $n$ về $0$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$.

Dữ liệu ra

In ra một số nguyên: số phép trừ ít nhất cần thực hiện để $n$ trở thành $0$.

Ràng buộc

• $0\le n\le {10}^{18}$

Ví dụ