NIO's Sword

题号：NC239621
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

See Problem N for PDF statements.

NIO is playing a new game. In this game, NIO has a sword with attack power represented by an integer $A$ . Initially, $A=0$ . There are also $n$ enemies in the game. NIO has to kill them in order, which means NIO must kill the $(i-1)$ -th enemy before killing the $i$ -th enemy for each $i$ ( $2\le i\le n$ ). For the $i$ -th enemy, NIO can kill it if and only if $A\equiv i \pmod{n}$ .

Fortunately, NIO can upgrade his sword at any moment for any number of times. Each time NIO upgrades his sword, he first chooses an integer $x$ ( $0\le x\le 9$ ), then changes the attack power of the sword from $A$ to $10\times A+x$ .

NIO wants to minimize the number of times to upgrade the sword so that he can win the game as fast as possible. Can you help him to find the minimum times?

输入描述:

The first line contains one integer  (), indicating the number of enemies.

输出描述:

Output one integer indicating the minimum times to upgrade the sword.

示例1

输入

复制

输出

复制

说明

Here is a possible solution for the example:

- The attack power of the sword when killing the first enemy can be .
- The attack power of the sword when killing the second enemy can be .
- The attack power of the sword when killing the third enemy can be .
- The attack power of the sword when killing the fourth enemy can be .

So he needs to upgrade the sword at least four times.