#include <stdio.h>
#include <string.h>

using namespace std;

FILE*f=fopen("prefix.in","r"),*g=fopen("prefix.out","w");

int l, aux[1000010], t, m;
char s[1000010];

int main()
{
    fscanf(f,"%d\n",&t);
    for(int j = 1; j <= t; j++)
    {
        fgets(s+1,1000002,f);
        m = strlen(s+1) - 1;
        l = 0;
        /*for(int i = 1; i <= m; i++)
            aux[i] = 0;*/
        int maxim = 0, h = 0, r = 0;
        for(int i = 2; i <= m; i++)
        {
            while(l > 0 && s[i] != s[l+1])
            {
                l = aux[l];
            }
            if(s[i] == s[l+1])
            {
                l++;
                aux[i] = l;
                if(i % l == 0)
                    r = l;
                if(l > maxim && ( (i % r) == 0) )
                {
                    maxim = l; h = i;
                }
            }
        }
            fprintf(g,"%d\n",h);
    }
    return 0;
}