chatday_nhan 2 ben

//
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


//=============================================================================
#include<iostream>
using namespace std;
int n;
int ans = 0;
void divisons(int n, int cnt) {
 
    if (cnt > ans) {
        ans = cnt;
    }
 
    if (n == 0) { 
        return;
    }
 
 
    for (int i = 10;i <= n;i *= 10) {
        divisons((n / i) * (n % i), cnt + 1);
    }
 
}
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1;test_case <= T;test_case++) {
        cin >> n;
        divisons(n, 0);
        cout << ans << endl;
        ans = 0;
    }
    return 0;
}