#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n;
namespace SAM{
	struct hzzdj{
		int len,father,son[30];
	}hz[N<<1];
	int tot,last;
	int mi[N<<1],siz[N];
	vector<int>E[N<<1];
	void init(){
		for(int i=0;i<=tot;i++){
			hz[i].len=hz[i].father=0;
			memset(hz[i].son,0,sizeof(hz[i].son));
			siz[i]=0;mi[i]=N+10;
			E[i].clear();
		}
		tot=0;last=0;hz[0].father=-1;
	}
	void insert(char ch,int i){
		int cha=ch-'a',p=last;
		int cur=++tot;hz[cur].len=hz[p].len+1;
		mi[cur]=i;siz[cur]=1;
		while(p!=-1&&!hz[p].son[cha]){
			hz[p].son[cha]=cur;
			p=hz[p].father;
		}
		if(p==-1)hz[cur].father=0;
		else{
			int q=hz[p].son[cha];
			if(hz[q].len==hz[p].len+1)hz[cur].father=q;
			else{
				int nq=++tot;hz[nq].len=hz[p].len+1;
				hz[nq].father=hz[q].father;
				hz[q].father=hz[cur].father=nq;
				memcpy(hz[nq].son,hz[q].son,sizeof(hz[q].son));
				while(p!=-1&&hz[p].son[cha]==q){
					hz[p].son[cha]=nq;;
					p=hz[p].father;
				}
			}
		}
		last=cur;
	}
	void dfs(int u){
		for(int v:E[u]){
			dfs(v);
			mi[u]=min(mi[u],mi[v]);
			siz[u]+=siz[v];
		}
	}
	int sol(){
		for(int i=1;i<=tot;i++)E[hz[i].father].push_back(i);
		dfs(0);
		int ans=n/2;
		for(int i=1;i<=tot;i++){
			if(siz[i]>=2){
				ans=max(ans,hz[i].len+(n-mi[i])/2);
			}
		}
		return ans;
	}
}
char ch[N];
void sol(){
	SAM::init();
	scanf("%s",ch+1);n=strlen(ch+1);
	for(int i=1;i<=n;i++)SAM::insert(ch[i],i);
	printf("%d\n",SAM::sol());
}
signed main(){
	int t;cin>>t;
	while(t--)sol();
	return 0;
}