rt。写了一晚上，一直在查是哪里tle了，写了一堆assert发现也没问题，求大佬看看到底哪里写挂了/kk

#include<bits/stdc++.h>
using namespace std;
int n,rs;
int dp[200005],len[200005],nxt[200005][26],fail[200005],pos[200005];
char s[200005],t[200005],l = 0,nw = 1,cnt =0 ;

void init(int n){
	for(int i =0;i<=n;i++)memset(nxt[i],0,sizeof(nxt[i])),dp[i] = 2000000005,fail[i] = 0,pos[i] = 0,len[i] = 0;
	rs = 0;l = 0;nw = 1;
	fail[0] = 1,len[1] = -1;fail[1] = 1;
	
}
void push_back(char c){
	t[++l] = c;
	int p = rs;
	while(l-len[p]-1<=0 or t[l]!=t[l-len[p]-1])p = fail[p],assert(++cnt<=10000000);
	if(!nxt[p][c-'a']){
		
		int k = fail[p],now = ++nw;
		len[now] = len[p]+2;
		while(l-len[k]-1<=0 or t[l]!=t[l-len[k]-1])k = fail[k],assert(++cnt<=10000000);
		fail[now] = nxt[k][c-'a'];
		nxt[p][c-'a'] = now;
		if(len[fail[now]]<=len[now]/2){
			pos[now] = fail[now];
		}else{
			k = pos[p];
			while(t[l]!=t[l-len[k]-1] or len[k]+2>len[now]/2)k = fail[k],assert(++cnt<=10000000);
			pos[now] = nxt[k][c-'a'];
		}
	}rs = nxt[p][c-'a'];
	return;
}void calc(){
	int ans = n;
	queue<int>q;
	for(int i = 2;i<=nw;i++)dp[i] = len[i];
	for(int i =0;i<4;i++)if(nxt[0][i])q.push(nxt[0][i]);
	while(!q.empty()){
		assert(++cnt<=10000000);
		int x=  q.front();q.pop();
		dp[x] = min(dp[x],dp[pos[x]]+1+len[x]/2-len[pos[x]]);
		//	cout << len[x] << " " << len[pos[x]] << " " << dp[x] << endl;
		ans = min(ans,n-len[x]+dp[x]);
		for(int i =0;i<4;i++){
			if(!nxt[x][i])continue;
			int y = nxt[x][i];
			dp[y] = min(dp[y],dp[x]+1);q.push(y);
		}
	}cout << ans << endl;return;
}
void solve(){
	scanf("%s",s+1);
	n=strlen(s+1);init(n);
	for(int i =1;i<=n;i++){
		if(s[i] == 'A')s[i] = 'a';
		if(s[i] == 'G')s[i] = 'b';
		if(s[i] == 'C')s[i] = 'c';
		if(s[i] == 'T')s[i] = 'd';
	}
	//for(int i = 1;i<=n;i++)cout << s[i];cout << endl;
	//init(n);
	for(int i = 1;i<=n;i++)push_back(s[i]);
	calc();return;
	
}
signed main(){
	int t;cin >> t;
	while(t--){
		solve();
	}
	return 0;
}