1 /* 4628 */ 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5  6 #define MAXN 17 7 #define INF    9999  8  9 char s[MAXN];10 char ss[MAXN];11 int dp[1<<MAXN];12 int len;13 14 inline int max(int a, int b) {15     return a>b ? a:b;16 }17 18 inline int min(int a, int b) {19     return a<b ? a:b;20 }21 22 bool isPalindrome(int x) {23     int i, j, l = 0;24     25     for (i=0, j=1; i<len; ++i, j<<=1)26         if (x & j)27             ss[l++] = s[i];28     29     i = 0;30     j = l-1;31     while (i<=j && ss[i]==ss[j])32         ++i, --j;33     if (i > j)34         return true;35     else36         return false;37 }38 39 int main() {40     int t;41     int i, j, k;42     43     #ifndef ONLINE_JUDGE44         freopen("data.in", "r", stdin);45     #endif46     47     scanf("%d", &t);48     while (t--) {49         scanf("%s", s);50         len = strlen(s);51         for (i=1; i<(1<<len); ++i) {52             dp[i] = INF;53             if (isPalindrome(i))54                 dp[i] = 1;55             else {56                 for (j=i; j; j=(j-1)&i)57                     dp[i] = min(dp[i], dp[j]+dp[i^j]);58             }59         }60         printf("%d\n", dp[(1<<len)-1]);61     }62     63     return 0;64 }