Digits

Time Limit: 1 s Memory Limit: 128 MB

Submission：56 AC：33 Score：98.48

Description

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₀, define a sequence using the following recurrence:

x_i+1 = 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

Input consists of several lines. Each line contains a value of x₀. Every value of x₀ 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₀ given in the input, output one line containing the smallest positive i such that x_i = x_i-1.

Samples

input

42 END

output