#include <fstream>

using namespace std;

char v[1000001];
int pred[1000001];

int main()
{
    ifstream in("prefix.in");
    ofstream out("prefix.out");

    int t,i,j,k;
    in>>t>>ws;
    for(i=0;i<t;i++)
    {
        in.getline(v+1,1000001);
        pred[1]=0; k=0;
        for(j=2;v[j];j++)
        {
            while(k>0 && v[j]!=v[k+1])
                k=pred[k];
            if(v[j]==v[k+1])
                k++;
            pred[j]=k;
        }
        j--;
        while(j>0 && !(pred[j]!=0 && j%(j-pred[j])==0))
            j--;
        out<<j<<"\n";
    }
    return 0;
}