G :: Generate random numbers

Time Limit: 10 Seconds    Memory Limit: 66560 KB

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₀, which has a decimal representation of length at most n. We then multiply the value a₀ 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₀=5555, a₀²=30858025, a₁=8580,...

Example 2: a₀=1111, a₀²=01234321, a₁=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₀ how many different numbers are produced.

Input

The input contains several test cases. Each test case consists of one line containing a₀ (0 < a₀ < 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.

Output

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₀. Note that a₀ should also be counted.

Sample Input

5555
0815
6239
0

Sample Output

32
17
111

Submit