#include <bits/stdc++.h>

using namespace std;

ifstream in("prefix.in");
ofstream out("prefix.out");

int const lim = 1000002;
char a[lim];
int n,k,pi[lim],t;

int main()
{
    in>>t;
    for(int i=1;i<=t;i++)
    {  int mx=0;
   in>>a+1;
   n=strlen(a+1);
   int r=0;
   k=0;
   pi[1]=0;
   for(int i=2;i<=n;i++)
   {
       while(k>0 && a[i]!=a[k+1])
        k=pi[k];

       if(a[i]==a[k+1])
        k++;

       pi[i]=k;
       if(pi[i]!=0 && pi[i]%(i-pi[i])==0)
        r=i;
   }
    out<<r<<'\n';
 }
}