Removing Digits

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Start from integer $n$. At each step, choose a nonzero digit of the current number and subtract it. Find the minimum number of steps to reach 0.

Input

The only line contains $n$.

Output

Print the minimum number of steps.

Subtasks

• Subtask 1 — 20 points: 1 <= n <= 100.
• Subtask 2 — 30 points: 1 <= n <= 10000.
• Subtask 3 — 50 points: 1 <= n <= 1000000.

Examples

Input

27

Output

5

Explanation

An optimal sequence is $27\to20\to18\to10\to9\to0$, using 5 steps.