5. Magic Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You consider a number to be "magic" if it has an even number of digits (not counting leading zeros), and if the first half of the number is equal to the second half of the number. For example, $$$13151315$$$, $$$878878$$$, and $$$9999$$$ are magic numbers, while $$$35353$$$, $$$12345$$$, and $$$3663$$$ are not.

You really like magic numbers, and you decide to play a game given a starting number $$$n$$$.

In one turn, you change the number $$$n$$$ depending on the following instructions:

  • If $$$n$$$ consists entirely of an odd number of nines (i.e. $$$99999$$$ or $$$9$$$), the game ends.
  • Otherwise, if $$$n$$$ is a magic number (as described above), you replace $$$n$$$ by the first half of its digits (so $$$13151315$$$ would become $$$1315$$$), which takes one turn.
  • Otherwise, you increase $$$n$$$ by $$$1$$$, which takes one turn.

It can be proven that the game will always end eventually.

Given these rules, figure out how many turns the game will take before the game ends.

Input

The only line of input contains a single positive integer $$$n$$$ $$$(1 <= n < 10^{12})$$$: the number you start out with.

Output

Output a single positive integer $$$t$$$: the number of turns you will end up taking before the game ends.

Scoring

Subtask 1 (6 points): $$$n$$$ <= $$$10^5$$$

Subtask 2 (18 points): no additional constraints

Examples
Input
86
Output
4
Input
7977
Output
14
Input
982490834438
Output
148563