Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Multiplicative Persistence

Limits: 1s, 512 MB

Multiplicative persistence proposes that any number can be expressed as a single digit number by multiplying the digits of the number and keep following the process with the result until the process throws a single digit number.

You are to write a program that when given a number will show how many steps it will take to make a single digit number number via multiplicative persistence method.

Input

Input file contains N arbitary integer numbers in N lines.

Constraints:

0<=N<=10^18

The program should read until the end of file.

Dataset is huge. Usage of faster I/O is advised.

Output

Print the number of steps described above on new lines.

Samples

InputOutput
391
873
125
3
4
2

Explanation:

Number given, 391.

Step -1: 3 * 9 * 1 = 27

Step -2: 2 * 7 = 14

Step -3: 1 * 4 = 4

Thus the answer is 3


Problem Setter: Niloy Sarker

Discussion
Submit

Login to submit