#include <iostream>
#include <cstdio>
#define milion 1000100
#include <cstring>
using namespace std;

int pref_max[10][milion],t,lun;
char sir[milion];

int caut(int l)
{
    for(int m=lun-1; m>0; --m)
            if ( pref_max[l][m] && m+1-pref_max[l][m] && ((m+1)%(m+1-pref_max[l][m]))==0)
                return m+1;
}

void rezolv()
{
    scanf("%d",&t);
    for (int l=1; l<=t; ++l)
    {
        scanf("\n");
        scanf("%s", sir);
        int maxl=0;
        lun=strlen(sir);
        int i=0,j=1;
        while (j<lun)

            if (sir[i]!=sir[j])
                if (i==0)
                    ++j;
                else
                    i=pref_max[l][i-1];

            else if (sir[i]== sir[j])
            {
                pref_max[l][j]=i+1;
                ++i;
                ++j;
            }
        maxl=caut(l);
        printf("%d\n",maxl);
    }

}

int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    rezolv();
    return 0;
}