#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("prefix.in");
ofstream fout ("prefix.out");
char p[1000002];
int n,maxi,pi[1000002];

void prefix(char p[],int &maxi)
{
    pi[0] = 0;
    int k = 0;
    int m=strlen(p);
    for (int q = 1; q < m; q++)
    {
        while ((k > 0) && (p[k] != p[q])) k = pi[k - 1];
        if (p[k] == p[q])k++;
        pi[q] = k;
       // if (pi[q]>maxi) maxi=pi[q];
        if (pi[q]>0&&!((q+1)%(q-pi[q]+1))) maxi=q+1;
    }
}
int main()
{
   fin>>n;fin.get();
   for (int i=1;i<=n;i++)
   {
       memset(pi,0,sizeof(pi));
       maxi=0;
       fin.getline(p,1000001);
       prefix(p,maxi);
       /*for (int j=0;j<strlen(p);j++)
       {
           fout<<pi[j]<<" ";

       }
       fout<<endl;*/
       fout<<maxi<<endl;
   }
    return 0;
}