#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;
}