Digits

Time limit1sMemory limit128 MB

Summary

Given a huge decimal number, repeatedly replace it with its digit count and report the first step where the value stops changing.

Level: Medium4 of 10
Topics: Math, Implementation, Simulation, String
Solved: No attempts yet

Problem

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_0$ , define a sequence by the recurrence

$x_{i+1} = \text{the number of digits in the decimal representation of } x_i.$

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

Input

The input consists of several lines. Each line contains a value of $x_0$ . Every value of $x_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_0$ in the input, output one line containing the smallest positive $i$ such that $x_i = x_{i-1}$ .

Examples1

Example 1
Input
```
42
END
```
Expected output
```
3
```