#include <bits/stdc++.h>
using namespace std;
int t;
const int N=2e5+5;
char s[N];
int n;
int len[N],tr[N][30],fail[N],trans[N],pos,tot=1,lst;
map<char,int> mp;

int getfail(int x,int i){
	while(s[i-len[x]-1]!=s[i]) x=fail[x];
	return x;
}

int ans;
int f[N];
void top(){
	for(int i=1;i<=tot;i++){
		f[i]=i;
	}
	queue<int> q;
	for(int i=1;i<=4;i++){
		if(tr[0][i]) q.push(tr[0][i]);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		f[u]=min(f[u],f[trans[u]]+1+len[u]/2-len[trans[u]]);
		ans=min(ans,n-len[u]+f[u]);
		for(int i=1;i<=4;i++){
			if(!tr[u][i]) continue;
			int v=tr[u][i];
			f[v]=min(f[v],f[u]+1);
			q.push(v);
		}
	}
}

int main(){
	cin>>t;
	mp['A']=1,mp['T']=2,mp['C']=3,mp['G']=4;
	while(t--){
		scanf("%s",s);
		n=strlen(s);
		fail[0]=1,len[1]=-1;
		for(int i=1;i<=tot;i++){
			for(int j=1;j<=4;j++){
				tr[i][j]=0;
			}
		}
		tot=1;
		for(int i=0;i<n;i++){
			int p=mp[s[i]];
			pos=getfail(lst,i);
			if(!tr[pos][p]){
				tr[pos][p]=++tot;
				len[tot]=len[pos]+2;
				fail[tot]=tr[getfail(fail[pos],i)][p];
				if(len[tot]<=2) trans[tot]=fail[tot];
				else{
					int tmp=trans[pos];
					while(s[i-len[tmp]-1]!=s[i]||((len[tmp]+2)<<1)>len[tot]) tmp=fail[tmp];
					trans[tot]=tr[tmp][p];
				}
			}
			lst=tr[pos][p];
		}
		ans=n;
		top();
		cout<<ans<<endl;
	}
}