#include <iostream>
#include <fstream>
#include <string.h>
#include <stdlib.h>
using namespace std;
ifstream in ("prefix.in");
ofstream out("prefix.out");
char s[1000003];
int lps[1000003], lenfin, len, t, dif;
int main()
{
    s[0]=' ';
    in.getline(s+1, 1000001); t=atoi(s+1);
    for(int q=1; q<=t; q++)
    {
        in.getline(s+1, 1000001);
        lps[1]=lenfin=len=0;
        for(int i=2; i<strlen(s); i++)
        {
            while(s[len+1]!=s[i]&&len>0)
                len=lps[len];
            if(s[len+1]==s[i])
                len++;
            lps[i]=len; dif=i-len;
            if(i%(i-len)==0&&lps[i-dif]==lps[i]-dif)
                lenfin=i;
        }
        out<<lenfin<<"\n";
    }
    return 0;
}