#include <bits/stdc++.h>
using namespace std;
namespace Le0{
const int N=1e5+5;
string s;
int n,ans,T,tot;
struct pam{
    int son[N][4],fl[N],ts[N],len[N],dp[N];
    int nt=1,now=0;
    int getfl(int p,int id){
        while(s[id-len[p]-1]!=s[id]) p=fl[p];
        return p;
    }
    int getts(int le,int p,int id){
        while(s[id-len[p]-1]!=s[id]||(len[p]+2)*2>le) p=fl[p];
        return p;
    }
    int iid(char c){
        if(c=='A') return 0;
        if(c=='T') return 1;
        if(c=='C') return 2;
        return 3;
    }
    void build(char c,int id){
        int p=getfl(now,id);
        if(!son[p][iid(c)]){
            fl[++nt]=son[getfl(fl[p],id)][iid(c)];
            len[nt]=len[p]+2;
            son[p][iid(c)]=nt;
            if(len[nt]<=2) ts[nt]=fl[nt];
            else if(len[nt]%2==0){
                ts[nt]=son[getts(len[nt],ts[p],id)][iid(c)];
            }
            if(len[nt]%2==0){
                dp[nt]=min(dp[p]+1,dp[ts[nt]]+1+len[nt]/2-len[ts[nt]]);
                ans=min(ans,dp[nt]+n-len[nt]);
            }
        }
        now=son[p][iid(c)];
    }
    void clear(){
        for(int i=0;i<=nt;i++){
            for(int j=0;j<4;j++) son[i][j]=0;
            fl[i]=len[i]=ts[i]=0;
            dp[i]=0x3f3f3f3f;
        }
    } 
}pm;
int main(){
    cin>>T;
    memset(pm.dp,0x3f,sizeof(pm.dp));
    while(T--){
        cin>>s;
        n=s.size();
        ans=n;
        tot+=n;
        s=" "+s;
        pm.len[1]=-1;
        pm.fl[0]=1;
        pm.dp[0]=1;
        for(int i=1;i<=n;i++){
            pm.build(s[i],i);
        }
        cout<<ans<<"\n";
        pm.clear();
    }
    // cout<<tot<<"\n";
    return 0;
}
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    return Le0::main();
}