//UVA11584PartitioningByPalindromes
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e3 + 5;
char vis[MAXN][MAXN], s[MAXN];
int dp[MAXN];//dp[i]为以第i个字母为结尾的最短回文单词
char bo[MAXN][MAXN];//记录两点之间是否存在回文
bool Is_palindrome(int i, int j) {
if(i >= j) return true;
if(s[i] != s[j]) return false;
if(vis[i][j]) return bo[i][j];
vis[i][j] = true;//记忆化搜索
bo[i][j] = Is_palindrome(i + 1, j - 1);
return bo[i][j];
}
int main() {
int n;
scanf("%d", &n);
while(n--) {
scanf("%s", s + 1);
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
dp[0] = 0;
int len = strlen(s + 1);
for(int i = 1; i <= len; i++) {
dp[i] = i;
for(int j = 0; j < i; j++) {
if(Is_palindrome(j + 1, i)) dp[i] = min(dp[i], dp[j] + 1);//若j+1与i之间有回文
//printf("dp = %d, i = %d\n", dp[i], i);
}
}
printf("%d\n", dp[len]);
}
return 0;
}
/*
3
racecar
fastcar
aaadbccb
*/
