#include <cstdio>
#include <string>
#include <bitset>

using namespace std;

#define Nmax 1000100

char a[Nmax];
int pi[Nmax];
bitset<Nmax> p;

int main()
 {
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);


        int n,i,T,k,max;

        scanf("%d\n",&T);


        while(T)
         {
         	fgets(a,Nmax,stdin);

                n = strlen(a) - 1;
                pi[0] = 0;
                k = 0;
                p = 0;
                max = 0;
                
                for(i=1;i<n;++i)
                 {
                  while((k > 0) && (a[k] != a[i]))
                   k = pi[k-1];

                  if(a[k] == a[i])
                   ++k;

                  pi[i] = k;

                  if(pi[i] > 0)
                   if((i+1) == 2*pi[i] || (p[pi[i]-1] == 1)&&((i+1)%(i-pi[i]+1) == 0))
                    p[i] = 1, max = i+1;
                 }
/*
                for(i=0;i<n;++i)
                 printf("%d ",pi[i]);
                printf("\n");
                for(i=0;i<n;++i)
                 printf("%d ",(int)p[i]);
                printf("\n");
*/

		printf("%d\n",max);
                --T;
         }


	return 0;
 }