//
//  main.cpp
//  Prefix
//
//  Created by Andrada Minca on 11.12.2025.
//

#include <fstream>
#define nmax (int)(1e6+1)
using namespace std;
ifstream cin("prefix.in");
ofstream cout("prefix.out");
int q,n,lps[nmax];
string s;
int solve()
{
    int i=1,len=0,sol=0;
    while(i<n)
    {
        if(s[i]==s[len])
        {
            len++;
            lps[i]=len;
            int p=i+1-lps[i];
            if(lps[i]%p==0)sol=i+1;
            i++;
        }
        else if(len==0)lps[i++]=0;
        else len=lps[len-1];
    }
    return sol;
}
int main()
{
    cin>>q;
    while(q--)
    {
        cin>>s;
        n=s.size();
        cout<<solve()<<'\n';
    }
    return 0;
}