#include <cstdio>#include <cstring>#include <algorithm> #include <vector>using namespace std;const int N=40005;char s[N];struct sam{	  int p,q,np,nq,cnt,last,a[N][26],l[N],f[N];	  sam(){cnt=0;last=++cnt;}	  void init(){	      cnt=0;last=++cnt;		  memset(a,0,sizeof(a));	      memset(l,0,sizeof(l));	      memset(f,0,sizeof(f));	  }	  void extend(int c){		    p=last;np=last=++cnt;l[np]=l[p]+1;		    while(!a[p][c]&&p)a[p][c]=np,p=f[p];		    if(!p)f[np]=1;		    else{			      q=a[p][c];			      if(l[p]+1==l[q])f[np]=q;			      else{				        nq=++cnt;l[nq]=l[p]+1;				        memcpy(a[nq],a[q],sizeof(a[q]));				        f[nq]=f[q]; f[np]=f[q]=nq;				        while(a[p][c]==q)a[p][c]=nq,p=f[p];			      }		    }	  }	  void solve(){	      init();	      scanf("%s",s);	      int n=strlen(s),len=n;	      for(int k=0;k<2;k++)for(int i=0;i<n;i++)extend(s[i]-‘a‘);	      int p=1;	      while(n--){	          for(int i=0;i<26;i++)if(a[p][i]){	              p=a[p][i];break;	          }	      }printf("%d\n",l[p]-len+1);	  }}sam;int T;int main(){    scanf("%d",&T);    while(T--)sam.solve();    return 0;}