Persistence

Interview

Time limit1sMemory limit256 MB

Summary

Count how many times multiplying the decimal digits together reduces the given number to a single digit.

Level: Easy1 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

Kipa likes multiplication. When Kipa sees a number, Kipa multiplies all of its digits together to build a new number, then repeats the same work on that new number. Once the number has only one digit there is nothing left to multiply, and Kipa becomes sad.

Write a program that prints how many steps Kipa's joy lasts. For example, $679$ shrinks like this.

$679 \to 6 \times 7 \times 9 = 378$ (step 1)
$378 \to 3 \times 7 \times 8 = 168$ (step 2)
$168 \to 1 \times 6 \times 8 = 48$ (step 3)
$48 \to 4 \times 8 = 32$ (step 4)
$32 \to 3 \times 2 = 6$ (step 5, the number now has one digit and Kipa becomes sad)

$679$ reaches one digit after 5 steps, so the answer is 5.

Input

The first line contains one integer $N$ with at most 9 digits and no leading zero. ( $1 \le N \le 999999999$ )

Output

Print the number of steps Kipa's joy lasts on the first line. If $N$ already has one digit, print 0.

Examples3

Example 1
Input
```
5
```
Expected output
```
0
```
Example 2
Input
```
10
```
Expected output
```
1
```
Example 3
Input
```
679
```
Expected output
```
5
```