Bad Random Numbers

Bessie wants to generate numbers that look random. She found an old description of the middle-square method, which works like this:

• Start from a four-digit number $N$ (with $1 \le N \le 9999$; a value with fewer than four digits is padded with leading zeros to make four).
• Take its middle two digits — the hundreds digit and the tens digit — and read them as a two-digit number.
• Square that two-digit number. The square is the next "random number" and also becomes the new starting number.

For example, starting from 7339:

 Num  Middle  Square
7339    33     1089
1089     8       64
  64     6       36
  36     3        9
   9     0        0
   0     0        0

By the pigeonhole principle the values must eventually repeat after at most 10000 steps. In the run above the sequence repeats after six generated numbers (once it reaches 0, every later number is also 0).

Some sequences repeat in a more complex way. Starting from 2245 the values alternate between 576 and 3249:

 Num  Middle  Square
2245   24      576
 576   57     3249
3249   24      576

Count how many random numbers are generated, starting from $N$, up to and including the first one that equals a value already present in the sequence. The starting number itself counts as already present. For 7339 this count is 6; for 2245 it is 3.

A single line containing one integer $N$ ($1 \le N \le 9999$).

Print a single integer: the number of random numbers generated by the middle-square method, starting from $N$, until it first produces a value that has already appeared in the sequence (the starting number counts as already appeared, and the repeating value itself is included in the count).