#include<stdio.h>
using namespace std;

const int NMAX = 1000005;
char s[NMAX];
int N,poz[NMAX];

int solve()
{

    int k = 0,ret =0;
    poz[1] = 0;
    int i;
    for(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;

    }
    for( ; i ; --i){
        if( poz[i] % (i - poz[i]) == 0 && poz[i] << 1 >= i){
            ret = i;
            i = 1;
        }
    }
    return ret;
}

int main()
{

    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d",&N);
    gets(s + 1);
    for( ; N ; --N){
        gets(s + 1);
        printf("%d\n",solve());
    }

    return 0;
}