# chatday_nhan 2 ben

duyvan
plain_text
6 months 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

//=============================================================================
#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;
}