Xóa chữ số (Removing Digits)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Bắt đầu từ số nguyên $n$. Mỗi bước chọn một chữ số khác 0 đang xuất hiện trong số hiện tại và trừ chữ số đó khỏi số. Hãy tìm số bước ít nhất để đạt 0.

Input

Dòng duy nhất chứa $n$.

Output

In số bước ít nhất.

Subtask

• Subtask 1 — 20 điểm: 1 <= n <= 100. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: 1 <= n <= 10000. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= n <= 1000000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

27

Output

5

Giải thích

Một đường tối ưu là $27\to20\to18\to10\to9\to0$, gồm 5 bước.