#include<bits/stdc++.h>
using namespace std;
struct node{
	int len,link,son[26];
}t[1000001];
int k,n,ans,tot,lst,siz[1000001],pos[1000001];
char s[500001];
basic_string <int> G[1000001];
void insert(int c){
	int cur=++tot,p=lst;
	t[cur].len=t[p].len+1;
	for(;p!=-1&&!t[p].son[c];p=t[p].link) t[p].son[c]=cur;
	if(p==-1) t[cur].link=0;
	else{
		int q=t[p].son[c];
		if(t[q].len==t[p].len+1) t[cur].link=q;
		else{
			t[++tot]=t[q];
			t[tot].len=t[p].len+1;
			t[cur].link=t[q].link=tot;
			for(;p!=-1&&t[p].son[c]==q;p=t[p].link) t[p].son[c]=tot;
		}
	}
	lst=cur;
}
void dfs(int x){
	for(int y:G[x]) dfs(y),siz[x]+=siz[y],pos[x]=min(pos[x],pos[y]);
}
int main(){
	memset(pos,0x3f,sizeof(pos));
	scanf("%d",&k);
	while(k--){
		scanf("%s",s+1),n=strlen(s+1),ans=n/2,tot=0,t[0].link=-1;
		for(int i=1;i<=n;i++) insert(s[i]-97),siz[lst]++,pos[lst]=i;
		for(int i=1;i<=tot;i++) G[t[i].link]+=i;
		dfs(0);
		for(int i=1;i<=tot;i++) if(siz[i]>1) ans=max(ans,t[i].len+(n-pos[i])/2);
		printf("%d\n",ans);
		for(int i=0;i<=tot;i++) G[i].clear(),pos[i]=1e9,siz[i]=t[i].len=t[i].link=0,memset(t[i].son,0,sizeof(t[i].son));
	}
	return 0;
}