#include <fstream>
#include <cstring>

using namespace std;
ifstream f("prefix.in");
ofstream g("prefix.out");
int t,z[1000005];
void Z(string s)
{
    for(int i=1,l=0,r=0;i<s.size();i++)
    {
        z[i]=0;
        if(i<=r)
        {
            z[i]=min(z[i-l],r-i+1);
        }
        while(i+z[i]<s.size() && s[z[i]]==s[i+z[i]])
        {
            z[i]++;
        }
        if(i+z[i]-1>r)
        {
            l=i;
            r=i+z[i]-1;
        }
    }
}
int main()
{
    f>>t;
    f.get();
    for(int test=1;test<=t;test++)
    {
        string s;
        getline(f,s);
        Z(s);
        int Max=0;
        for(int i=1;i<s.size();i++)
        {
            if(z[i]>=i)
            {
                Max=max(Max,(z[i]+i)/i*i);
            }
        }
        g<<Max<<'\n';
    }
    return 0;
}