#define _CRT_SECURE_NO_WARNINGS #include <cstdio>#include <cstring>#include <algorithm>#include <numeric>using namespace std;int T;char str[1005];int len;int s[1005][1005]; // s[i][j] == 1 --> str[i..j] is palindromeint d[1005];#define INF 10000// void setPalindrome(int left, int right, int len){    int l = left, r = right;    while (l >= 0 && r < len && str[l] == str[r]){        s[l][r] = 1;        l--; r++;    }}/*这种做法会超时，类似矩形连乘，O(n*n*n)void setPalindrome(int left, int right, int len){    int l = left, r = right;    while (l >= 0 && r < len && str[l] == str[r]){        d[l][r] = 1;        l--; r++;    }}int dp(int i, int j){    if (d[i][j] > 0)        return d[i][j];    d[i][j] = INF;    for (int k = i; k < j; k++){        d[i][j] = min(d[i][j], dp(i, k) + dp(k + 1, j));    }    return d[i][j];}int main(){    scanf("%d", &T);    while (T--){        scanf("%s", str);        len = strlen(str);        memset(d, 0, sizeof(s));        for (int i = 0; i < len; i++){            setPalindrome(i, i, len); // center is str[i]            setPalindrome(i, i + 1, len); // center is between str[i] and str[i+1]        }        printf("%d\n", dp(0, len - 1));    }    return 0;}*/int main(){    scanf("%d", &T);    while (T--){        scanf("%s", str);        len = strlen(str);        memset(s, 0, sizeof(s));        for (int i = 0; i < len; i++){            setPalindrome(i, i, len); // center is str[i]            setPalindrome(i, i + 1, len); // center is between str[i] and str[i+1]        }        for (int j = 0; j < len; j++){            d[j] = INF;            for (int i = 0; i <= j; i++){                if (s[i][j]){                    if (i == 0){                        d[j] = 1;                        break;                    }                    else                        d[j] = min(d[j], d[i - 1] + 1);                }            }        }        printf("%d\n", d[len - 1]);    }    return 0;}