1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1e3 + 5; 4 int dp[N][N], inf = 1e9; 5 char str[N]; 6 bool judge(int l, int r) { 7     for(int i = l - 1, j = r - 1; i < j; ++i, --j) { 8         if(str[i] != str[j]) 9             return false;10     }11     return true;12 }13 int dfs(int l, int r) {14     if(l == r)15         return dp[l][l] = 1;16     if(l > r)17         return 0;18     if(dp[l][r] < inf)19         return dp[l][r];20     int ans = inf;21     for(int i = r; i >= l; --i) {22         if(judge(i, r))23             ans = min(ans, dfs(l, i - 1) + 1);24     }25     return dp[l][r] = ans;26 }27 28 int main()29 {30     int t;31     scanf("%d", &t);32     for(int ca = 1; ca <= t; ++ca) {33         scanf("%s", str);34         int len = strlen(str);35         for(int i = 1; i <= len; ++i) {36             for(int j = 1; j <= len; ++j) {37                 dp[i][j] = inf;38             }39         }40         printf("Case %d: %d\n",ca, dfs(1, len));41     }42     return 0;43 }