#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;

}