Time Limit: 5000 ms
Memory Limit: 65535 ms
John von Neumann suggested in 1946 a method to create a sequence of pseudo-random numbers. His idea is known as the "middle-square"-method and works as follows: We choose an initial value a0, which has a decimal representation of length at most n. We then multiply the value a0 by itself, add leading zeros until we get a decimal representation of length 2 × n and take the middle n digits to form ai. This process is repeated for each ai with i>0. In this problem we use n = 4.
Example 1: a0=5555, a02=30858025, a1=8580,...
Example 2: a0=1111, a02=01234321, a1=2343,...
Unfortunately, this random number generator is not very good. When started with an initial value it does not produce all other numbers with the same number of digits.
Your task is to check for a given initial value a0 how many different numbers are produced.