Bajtynka received a new logic toy from Bajtazar for her birthday – a cyclic lock. The cyclic lock consists of two buttons and a display. The display can show an arbitrarily large number in decimal notation without leading zeros. Initially, the display shows a number chosen by the toy's software.

The goal of the game is to make the number $1$ appear on the display. To achieve this, you can use the two aforementioned buttons. Pressing the first button increases the number by $1$. The second button cyclically rotates the decimal representation of the number by one position, such that the most significant digit moves to the least significant position, and then all leading zeros are removed.

For example, after pressing the first button, the number $99$ changes to $100$. After pressing the second button, the number $143$ changes to $431$, while the number $700523$ changes to $5237$.

Now Bajtynka wonders what the minimum number of button presses is needed to solve the puzzle. Your task is to determine this number.

Input

The first and only line of input contains a single number $n$ representing the currently displayed number ($1 \le n \le 10^{1\,000\,000}$).

Output

Your program should output a single number representing the minimum number of button presses needed to solve the puzzle.

Examples

Input 1

301

Output 1

17

Note 1

To solve the puzzle in $17$ moves, you must: 1. press the first button eight times; the toy will then display $309$, 2. press the second button; the toy will then display $93$, 3. press the first button seven times; the toy will then display $100$, 4. press the second button to solve the puzzle.

Sample tests: Test $0$ is the test from the example above. Additionally: $1$: $n = 1\,000\,000$; the answer is $1$; $2$: $n = 9\,908\,999$; the answer is $6$; $3$: $n = 9 \cdot 10^{999\,999}$; the answer is $3$.

Subtasks