**6 人解决**，8 人已尝试。

**6 份提交通过**，共有 13 份提交。

**6.6** EMB 奖励。

**单点时限: **2.0 sec

**内存限制: **256 MB

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 a_{0}, which has a decimal representation of length at most n. We then multiply the value a_{0} by itself, add leading zeros until we get a decimal representation of length 2 × n and take the middle n digits to form a_{i}. This process is repeated for each a_{i} with i>0. In this problem we use n = 4.

Example 1: a_{0}=5555, a_{0}^{2}=30858025, a_{1}=8580,…

Example 2: a_{0}=1111, a_{0}^{2}=01234321, a_{1}=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 a_{0} how many different numbers are produced.

The input contains several test cases. Each test case consists of one line containing a_{0} (0 < a_{0} < 10000). Numbers are possibly padded with leading zeros such that each number consists of exactly 4 digits. The input is terminated with a line containing the value 0.

For each test case, print a line containing the number of different values a_{i} produced by this random number generator when started with the given value a_{0}. Note that a_{0} should also be counted.

Input

5555 0815 6239 0

Output

32 17 111

**6 人解决**，8 人已尝试。

**6 份提交通过**，共有 13 份提交。

**6.6** EMB 奖励。

题目标签