1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int mp[101][101];
int zip(string &input, int start, int end);
int count(int a);
int main() {
    int T;
    cin >> T;
    string input;
    while(T--) {
        cin >> input;
        int len = input.length();
        for(int i=len-1; i>=0; --i) {
            for(int j=i; j<len; ++j) {
                int temp = j-i+1;
                mp[i][j] = temp;
                if( temp <= 4 )
                    continue;
                mp[i][j] = min(mp[i][j], zip(input, i, j));
                for(int k=i ;k<j; ++k) {
                    mp[i][j] = min(mp[i][k] + mp[k+1][j], mp[i][j]);
                }
            }
        }
        cout << mp[0][len-1] << endl;
    }
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX