#include <iostream>

#include <cstring>

#include <cstdio>

#include <map>

#include <algorithm>

#define mst(a,b)    memset(a,b,sizeof(a))

#define lowbit(x)   (x&(-x))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

const int mod=1e9+;

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e6+;

char x[maxn];

int nx[maxn];

void init(int m){

    int i=,j=nx[]=-;

    while(i<m){

        while(-!=j and x[i]!=x[j])j=nx[j];

        nx[++i]=++j;

    }

}

int mx[maxn];

int solve(){

    cin>>x;

    int n=strlen(x);

    init(n);

    for(int i=;i<=n;++i)

        mx[i]=;

    for(int i=n-;i;--i){

        if(nx[i]>){

            mx[nx[i]]=max(mx[nx[i]],mx[i]);

            mx[nx[i]]=max(mx[nx[i]],min(n-i,i/));

        }

    }

    int ans=;

    for(int i=nx[n];i>;i=nx[i])

        if(mx[i]>=i)ans=max(ans,i);

    return ans;

}

int main(){

#ifdef local

    freopen("in.txt","r",stdin);

#endif

    ios::sync_with_stdio(false);

    cin.tie(); cout.tie();

    int T;cin>>T;

    while(T--)

        cout<<solve()<<"\n";

    return ;

}