11634 - Generate random numbers

John von Neumann於1946年提出一個方法，能產生出一組虛擬的隨機數字，該方法被稱為"中間平方法"(middle-square)，其作法如下：選擇一 個初始值 a0，該值以十進位表示的長度最長為 n，將 a0 取平方後在前面補 0 直到長度為 2 x n，並取中間的 n 個位數得到 a1，以此類推可得到a2, a3...。例如當 n = 4時：

例1：a0 = 5555, a0^2 = 30858025, a1 = 8580。
例2：a0 = 1111, a0^2 = 01234321, a1 = 2343。

可惜的是這個方法不夠好，它無法產生出所有相同長度的數字。本題給定 a0，請你計算共可產生出幾個數字。

Input Specification

輸入有多筆測試資料，每筆一列包含一整數 a0 (0 < a0 < 10000)，請以 0 填滿長度不足4的數字前面，使每個數字長度皆為4個位數。當a0=0表示測試資料結束。

Output Specification

請計算每組資料中，以a0開始共可產生出幾個不同的數字，a0本身必需算在裡面。

Sample Input

5555
0815
6239
0

Sample Output

32
17
111

---

原文出處