407968: GYM102953 5 Magic Numbers

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.

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

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

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

Subtask 2 (18 points): no additional constraints

86

4

7977

14

982490834438

148563