Making Random Numbers

In 1946, John von Neumann proposed a method for generating a sequence of pseudo-random numbers. It is known as the middle-square method and works as follows.

First, choose an initial value $a_0$. When written in decimal, $a_0$ must have at most $n$ digits. Next, square $a_0$ and pad the result with leading zeros until it has $2n$ digits. The middle $n$ digits of this $2n$-digit number become $a_1$. Repeating the same rule yields $a_i$ for every $i > 0$. In this problem, $n = 4$ is fixed.

Example 1: If $a_0 = 5555$, then $a_0^2 = 30858025$, so taking the middle four digits gives $a_1 = 8580$.

Example 2: If $a_0 = 1111$, then $a_0^2 = 01234321$ (padded with a leading zero to eight digits), so $a_1 = 2343$.

In fact, this is not a good random number generator: the sequence eventually reproduces a value it has generated before and falls into a cycle.

Given $a_0$, write a program that determines how many distinct numbers the sequence produces before it repeats a value for the first time.

The input consists of several test cases. Each test case is a single line containing one integer $a_0$ ($0 < a_0 < 10000$). If $a_0$ does not have four digits, it is written with leading zeros to make four digits. The last line of the input contains a single $0$, which is not processed.

For each test case, print on one line the number of distinct values $a_i$ that appear in the sequence. Count $a_0$ as well.