#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <iostream>using namespace std;class SuffixArray{public: int *sa,*rank; int *height,*rmq,*mm,*best[21]; int keyTypeMax,length; SuffixArray(int *a,int n,int m) { keyTypeMax = max(m,n)+5; sa = new int[n+10]; rank = new int[keyTypeMax]; height = new int[n+10]; rmq=new int[n+10]; mm=new int[n+10]; for(int i=0;i<21;i++) best[i]=new int[n+10]; length = n+1; a[n] = 0; setSa(a); setHeight(a); init_rmq(n); } void setSa(int *a) { int *cnt = new int[keyTypeMax]; for(int i=0; i<keyTypeMax; i++) cnt[i] = 0; for(int i=0; i<length; i++) cnt[rank[i] = a[i]]++; for(int i=0; i<keyTypeMax-1; i++) cnt[i+1] += cnt[i]; for(int i= length-1; i >= 0; i--) sa[--cnt[rank[i]]] = i; int *rankSt = new int[keyTypeMax]; int *rankStPos = new int[length+10]; for(int p=0,h=1,rankMax=keyTypeMax; p<length; h<<= 1,rankMax=p) { p = 0; for(int i=length-h;i<length;i++) rankStPos[p++] = i; for(int i=0; i<length; i++) if(sa[i]>=h) rankStPos[p++] = sa[i] - h; for(int i=0; i<length; i++) rankSt[i] = rank[rankStPos[i]]; for(int i=0; i<rankMax; i++) cnt[i] = 0; for(int i=0; i<length; i++) cnt[rankSt[i]]++; for(int i=0; i<rankMax-1; i++) cnt[i+1] += cnt[i]; for(int i=length-1; i>=0; i--) sa[--cnt[rankSt[i]]] = rankStPos[i]; swap(rank,rankSt); rank[sa[0]] = 0; p=1; for(int i=1;i<length;i++) { if(rankSt[sa[i]]==rankSt[sa[i-1]] &&rankSt[sa[i]+h]==rankSt[sa[i-1]+h]) rank[sa[i]] = p-1; else rank[sa[i]] = p++; } } delete(rankStPos); delete(rankSt); delete(cnt); } void setHeight(int *a) { int h = 0; for(int i=0; i<length; i++) { int r = rank[i]; if(!r) height[r] = h = 0; else { int pb = sa[r-1]; int off; for(off = (h?h-1:0); a[i+off]==a[pb+off]; off++) ; height[r] = h = off; } } } void init_rmq(int n) { mm[0]=-1; for(int i=1;i<=n;i++) rmq[i]=height[i]; for(int i=1;i<=n;i++) mm[i]=(i&(i-1))?mm[i-1]:(mm[i-1]+1); for(int i=1;i<=n;i++) best[0][i]=i; for(int i=1;i<=mm[n];i++) { for(int j=1;j<=n+1-(1<<i);j++) { int a=best[i-1][j],b=best[i-1][j+(1<<(i-1))]; best[i][j]=rmq[a]<rmq[b]?a:b; } } } int ask_rmq(int a,int b) { int t=mm[b-a+1];b-=(1<<t)-1; a=best[t][a];b=best[t][b]; return rmq[a]<rmq[b]?a:b; } int lcp(int a,int b) { a=rank[a];b=rank[b]; if(a>b) swap(a,b); return height[ask_rmq(a+1,b)]; }};const int maxn=1000001;int s[maxn];char c[maxn];void solve(int *s,int n){ SuffixArray sa(s,n,256); int ans=0; for(int l=1;l<=n;l++) { for(int i=l;i<=n;i+=l) { int k=sa.lcp(i-l,i); int r=k/l+1; int t=i-l+k%l-l; if(t>=0&&k%l!=0) { if(sa.lcp(t,t+l)/l+1>r) r++; }if(r==1) continue;ans=l;break; } } cout<<ans<<endl;}int main(){ int ca;for(scanf("%d",&ca);ca--;) {scanf("%s",c); int n=strlen(c); for(int i=0;i<n;i++) s[i]=int(c[i]); solve(s,n); } return 0;}
