In this problem you will be given a number as the starting member of a sequence.You can try growing the sequence by splitting this number into atleast two parts and then multiplying the parts together to get the next number of the sequence.So, if the starting number is 234 then possible splits are {2, 34}, {23, 4}, {2, 3, 4} and hence the possible successors of 234 in the respective sequences can be 68, 92 and 24. Lets suppose that we choose 68 as the successor. The next possible number is the only one i.e. 48 and this you get by splitting 68 as {6, 8} and multiplying 6 and 8. If you continue in similar fashion until you get a single digit number then the sequence we will get will be {234, 68, 48, 32, 6}. So, you get a 5 membered sequence. Had you would have chosen 92 as the second member the sequence would have been {234, 92, 18, 8} and for 24 it would have been {234, 24, 8}. So, The longest sequence that you get is of length 5. So, in this problem you are supposed to find the length of the longest sequence of all the sequences possible starting from the given number N.

Input

First line gives the number of test cases T. T lines follow each containg only one integer N, the starting member of the sequnece.

Output

One line for each test case containg the length of the longest sequence possible.

Limits

1<=T<=100
1<=N<=100000

Sample Input

4
234
55
686
6

Sample Output

5
4
7
1

Problem Setter: Dhruva Bhaswar

Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0