Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C, C++, Java 11, JAVA 8, Python, ZIG

A googol written out in decimal has 101 digits. A googolplex has one plus a googol digits. That’s a lot of digits! Given any number x_0x_0, define a sequence using the following recurrence:

x_{i+1} =x_{i+1} = the number of digits in the decimal representation of x_ix_i

Your task is to determine the smallest positive ii such that x_i = x_{i-1}x_i = x_{i-1}.

Input

Input consists of several lines. Each line contains a value of x_0x_0. Every value of x_0x_0 is non-negative and has no more than one million digits. The last line of input contains the word END.

Output

For each value of x_0x_0 given in the input, output one line containing the smallest positive ii such that x_i = x_{i-1}x_i = x_{i-1}.

Sample Input

42
END

Sample Output

3

x_0 = 42, x_1 = 2, x_2 = 1, x_3 = 1x_0 = 42, x_1 = 2, x_2 = 1, x_3 = 1


Comments

There are no comments at the moment.