#include <iostream>
#include <cstdio>
#include <string.h>
#define NMax 1000025
using namespace std;
char A[NMax];
long long int mx,nro,pi[NMax],n;
void prefix();
int main()
{
    int nr,i;
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    cin >> nr;
    fgets(A,sizeof(A),stdin);
    for(i=1;i<=nr;i++)
    {
        fgets(A+1,sizeof(A),stdin);
        A[0]=' ';
        n=strlen(A)-2;
        prefix();
        if(nro==0) cout << 0 << endl;
        else
        {
            int aux;
            aux=mx-nro;
            if(mx%aux!=0)
                cout << mx-mx%aux << endl;
            else
                cout << mx << endl;

        }
    }
    return 0;
}
void prefix()
{
    int q=0,i;
    mx=0;nro=0;
    pi[1]=0;
    for(i=2;i<=n;i++)
    {
        if(q&&A[q+1]!=A[i])
            q=pi[q];
        if(A[q+1]==A[i])
        {
            q++;
            if(q>nro)
        {
            mx=i;
            nro=q;
        }
        }
        pi[i]=q;
    }

}