#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

ifstream fin("prefix.in"); ofstream fout("prefix.out");
#define cin fin
#define cout fout



int t, n, m, k, a[300010], q, l, r;
char s[1000010];
int pi[1000010];
bool comp[1000010];


int32_t main(){
INIT
cin>>t;
cin.get();
while(t--){
    cin.getline(s, 1000000); n=strlen(s);
    pi[0]=0;
    int ml=0;
    comp[0]=false;
    for(int i=1; i<n; i++){
            comp[i]=false;
        int l0=pi[i-1];
        while(s[l0]!=s[i] && l0>0){
            l0=pi[l0-1];
        }
        if(s[i]==s[l0]){
            l0++; pi[i]=l0;
        }
        else{
            pi[i]=0;
        }

        int k1=(i+1)-pi[i];
        int k2=(i+1-k)-pi[i-k];
        if( (k1==k2) && (k1>0) && (pi[i]>0) && (comp[k1]==false) && ( ((i+1)%k1)==0 ) ){
            ml=i+1;
        }
        else{
            if( ((i+1)%k1)==0 ){
                comp[k1]=true;
            }
        }

    }
    cout<<ml<<"\n";
}



return 0;
}