/*
状态压缩DP
dp[ i ]:达到i状态的最小step。
题意：每次可以去掉一个回文串，求最少几步能取完。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<math.h>
using namespace std;
typedef long long ll;
//typedef __int64 int64;
const int maxn = ;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps = 1e-;
int dp[ <<maxn ];
char s[ maxn ];
int state[ <<maxn ];//回文的状态
bool JudgeOneZero( int ss,int len ){
int Index[ maxn ];
int cc = ;
int IndexOfString = ;
while( IndexOfString<len ){
if( ss%== ){// 所有的 “1” 代表该位置上有字母，即这些组合是回文串
Index[ cc++ ] = IndexOfString;
}
ss /= ;
IndexOfString++;
}
if( cc== ) return true;
int L,R;
L = ;
R = cc-;
while( L<=R ){
if( s[Index[L]]!=s[Index[R]] ) return false;
L++;
R--;
}
return true;
}//判断s是否是回文状态
int init_state( int len ){
int cnt = ;
int N = <<len;
state[ cnt++ ] = ;
for( int i=;i<N;i++ ){
if( JudgeOneZero( i,len )==true ){
state[ cnt++ ] = i;
}
}
return cnt;
} //初始化回文的状态
bool Judge( int cur,int nxt,int len ){//当前状态cur，前一状态nxt
int Index[ maxn ];
int cc = ;
int IndexOfString = ;
while( IndexOfString<len ){
if( cur%== ){
if( nxt%== ) return false;
}//当前状态为1，前一状态必须为1
if( nxt%== ){
if( cur%== ) return false;
}//前一状态是0，当前状态也必须是0
if( cur%==&&nxt%== ){
Index[ cc++ ] = IndexOfString;
}
IndexOfString++;
cur /= ;
nxt /= ;
}
if( cc== ) return true;
int L,R;
L = ;
R = cc-;
//printf("cc=%d\n",cc);
while( L<=R ){
if( s[Index[L]]!=s[Index[R]] ) return false;
L++;
R--;
}
return true;
}
int main(){
int T;
scanf("%d",&T);
while( T-- ){
scanf("%s",s);
int n = strlen(s);
int cnt = init_state( n );
int N = (<<n);
for( int i=;i<N;i++ )
dp[ i ] = inf;
dp[ N- ] = ;
/*
for( int i=N-2;i>=0;i-- ){
for( int j=0;j<N;j++ ){
if( i==j ) continue;
if( Judge( i,j,n )==true ){
//printf("i=%d, j=%d\n",i,j);
dp[ i ] = min( dp[i],dp[j]+1 );
//printf("dp[%d] = %d\n\n",i,dp[i]);
}
}
}
*/
for( int i=N-;i>=;i-- ){
for( int j=;j<cnt;j++ ){
if( ==(i&state[j]) ){
dp[ i ] = min( dp[i],dp[state[j]|i]+ );
}
}
}
printf("%d\n",dp[]);
}
return ;
}