#include <bits/stdc++.h>

using namespace std;

ifstream f("prefix.in");
ofstream g("prefix.out");

int t,k,poz;
string s;
int main()
{
    f>>t;
    while(t--)
    {
        f>>s;
        vector <int> pi(s.size());
        pi[0]=k=poz=0;
        for(int i=1; i<s.size(); i++)
        {
            while(k!=0 and s[k]!=s[i])
            {
                k=pi[k-1];
            }
            if(s[k]==s[i])
                k++;
            pi[i]=k;
            if((i+1)%(i-pi[i]+1)==0 and pi[i]!=0)
                poz=i+1;
        }
        g<<poz<<'\n';
    }
    return 0;
}