#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int NMAX = 1000005;

char s[NMAX];
int z[NMAX];

int main(){
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    int tests;
    scanf("%d\n",&tests);
    for(;tests;tests--){
        scanf("%s",s);
        int n=strlen(s);

        ///make z function
        z[0]=0;
        for(int k=1,st=0,dr=0;k<n;++k){
            if(k>dr){
                st=dr=k;
                while(dr<n && s[dr]==s[dr-st])
                    dr++;
                z[k]=dr-st;
                dr--;
            }else{
                if(k+z[k-st]<=dr)
                    z[k]=z[k-st];
                else{
                    st=k;
                    while(dr<n && s[dr]==s[dr-st])
                        dr++;
                    z[k]=dr-st;
                    dr--;
                }
            }
        }
        ///iterate to get answer
        int ans=0;

        for(int i=1;i<n;++i){
            if(z[i]>=i)
                ans=max(ans,(z[i]/i+1)*i);
        }
        printf("%d\n",ans);
    }
    return 0;
}