#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)&&((i+1) == 2*pi[i] || (p[pi[i]-1] == 1)&&((i+1)%(i-pi[i]+1) == 0)))
                    p[i] = 1, max = i+1;
                 }
                 
		printf("%d\n",max);
         }


	return 0;
 }