Untitled

mail@pastecode.io avatar
unknown
plain_text
14 days ago
1.9 kB
0
Indexable
Never
Card game designer Mr. JongMin came up with a new game, rules are as follows:



The cards are numbered from number 0 to 9:
-> At the start of the game you get 5 cards, where first card would always be nonzero
-> Without changing order of cards, cards are divided into two parts.
-> Now multiply these two numbers which are obtained by these two parts
-> You would get cards corresponding to this new number
-> When the cards that you have cannot be divided into two groups, the game is over.


For example initially we got the cards 1, 2, 3, 4 and 5; these were divided by us into 1, 2, and 3, 4, 5. So the cards that we will get in the next round are 12 x 345 = 4140. This process is then continued in the following manner:


4140 -> 41 x 40 = 1640 -> 16 x 40= 640 -> 6 x 40 = 240-> 2 x 40 = 80 -> 8 x 0 = 0


So the cards were divided 6 times in this case.
The goal is to maximize the number of divisions we can perform in order to win the game. 

Input
First line is a number T, indicating the number of test cases that follow.
Each test case consists of a number N which indicates the initial set of cards given to us.

Output
Print the maximum number of divisions that can be performed with the provided set of cards on each line. 

I/O Example
(input)
2
12345
6789

(output)

10
11


Constraints
1<=T<=50
1<=Number of digits in N<=5

Output:
10
11
21
5
12
16
19
16
1
1
1
28
1
0
0
0
8
5
10
4
3
2
2
20
14
9
4
1
1
8
0
3
3
12
13
26
12
19
12
20
14
4
9
22
20
26
10
8
0
18

Input:
50
12345
6789
98765
11111
22222
33333
44444
55555
10000
20000
30000
99999
90000
2
3
1
786
456
2392
10203
20405
10001
20004
67089
30555
12340
12300
300
800
999
7
10101
11100
13579
24680
97531
86420
36912
48120
88888
80808
80008
777
65432
33777
99888
12321
23570
9
89012
Leave a Comment