Bessie is trying to generate random numbers. She stumbled upon an old reference to the 'middle square' method for making numbers that appear to be random. It works like this:
* Pick a starting four digit number (1 <= N <= 9999)
* Extract its middle two digits (the hundreds and tens digit) as a number
* Compute the square of those two digits
* That square is the 'random number' and becomes the new starting number
Here's a sample:
Num Middle Square
7339 33 1089
1089 8 64
64 6 36
36 3 9
9 0 0
0 0 0
The 'pigeon hole principle' tells us that the random numbers surely must repeat after no more than 10,000 of them -- and the sequence above repeats after just six numbers (the next number and all subsequent numbers are 0).
Note that some sequences repeat in a more complex way; this one alternates back and forth between 576 and 3249:
Num Middle Square
2245 24 576
576 57 3249
3249 24 576 Your job is to tell Bessie the count of 'random numbers' that can be generated from a starting number before the sequence repeats a previously seen number. In the first case above, the answer is '6'. In the 'alternating' case, the answer is '3'.