### Problem Statement

We start with an integer and create a sequence of successors using the following procedure: First split the decimal representation of the given number into several (at least two) parts, and multiply the parts to get a possible successor. With the selected successor, we repeat this procedure to get a third number, and so on, until we reach a single-digit number.

For example, let's say we start with the number 234. The possible successors are:

• 23 * 4 = 92,
• 2 * 34 = 68 and
• 2 * 3 * 4 = 24.
If we select 68 as the successor, we then generate 6 * 8 = 48 (the only possibility), from this we generate 4 * 8 = 32 and finally 3 * 2 = 6. With this selection, we have generated a sequence of 5 integers (234, 68, 48, 32, 6).

Given the starting number, start, return the length of the longest sequence that can be generated with this procedure. In the example, the given sequence would be the longest one since the other selections in the first step would give the sequences: (234, 92, 18, 8) and (234, 24, 8), which are both shorter than (234, 68, 48, 32, 6).

### Definition

 Class: NumberSplit Method: longestSequence Parameters: int Returns: int Method signature: int longestSequence(int start) (be sure your method is public)

### Notes

-There can not exist an infinite sequence.
-Although we use no leading zeros in the decimal representation of the number we start with, the parts we get by splitting the number may have leading zeros (e.g. from 3021 we can get 3 * 021 = 63).

### Constraints

-start is between 1 and 100000, inclusive.

### Examples

0)

 `6`
`Returns: 1`
 A single-digit number is already the last number.
1)

 `97`
`Returns: 4`
 For two-digit numbers, there is always only one possible sequence. Here: 97 -> 63 -> 18 -> 8 (4 numbers).
2)

 `234`
`Returns: 5`
 The example from the problem statement.
3)

 `876`
`Returns: 7`
 Here, it is optimal to make a three way split in the first step - i.e. use 8*7*6=336 as the first successor. Although a two way split would lead to a larger number (87*6=522 or 8*76=608), both these choices would lead in the end to a shorter sequence. The optimal sequence is: 876, 8*7*6=336, 33*6=198, 19*8=152, 1*52=52, 5*2=10, 1*0=0.
4)

 `99999`
`Returns: 29`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4451

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7217&pm=4451

gepa

#### Testers:

PabloGilberto , lbackstrom , brett1479

#### Problem categories:

Dynamic Programming, Graph Theory, Simple Math