407968: GYM102953 5 Magic Numbers

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

5. Magic Numberstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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

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

加入题单

上一题 下一题 算法标签: