#include<iostream>
#include<stack>
#include<deque>
#include<queue>
#include<string>
#include<vector>
#include<algorithm>
#include<fstream>
#include<string.h>
#include<stdio.h>
using namespace std;
ifstream in("prefix.in");
ofstream out("prefix.out");
const int NMAX = 1000005;
char s[NMAX];
int N,poz[NMAX],M;

int solve()
{

    int k = 0,ret =0;
    poz[1] = 0;
    for(int i = 2 ; s[i] ; ++i){
        while(k && s[k + 1] != s[i])
            k = poz[k];
        if(s[k+1] == s[i])
            ++k;
        poz[i] = k;
        if( poz[i] % (i - poz[i]) == 0 && poz[i] *2 >= i)
            ret = i;
    }
    return ret;
}

int main()
{

    (in>>N).ignore(1);
    for( ; N ; --N){
        in.getline(s + 1,NMAX);
        out<<solve()<<"\n";
    }
    in.close();
    out.close();
    return 0;
}