原题链接：https://vjudge.net/problem/UVA-11584
分类：线性结构
备注：LIS变形

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
char s[maxn];
bool check(int st,int ed){
    for(int i=st,j=ed;i<j;i++,j--)
        if(s[i]!=s[j])return false;
    return true;
}
int t,d[maxn];
int main(void){
    // freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%s",s+1);
        for(int i=1;i<=strlen(s+1);i++){
            d[i]=d[i-1]+1;
            for(int j=0;j<i;j++){
                if(check(j+1,i))
                    d[i]=min(d[i],d[j]+1);
            }
        }
        printf("%d\n",d[strlen(s+1)]);
    }
    return 0;
}