#include<cstdio>
#include<cstdlib>
using namespace std;
char *fileData;
char *endOfFile;
char *A;
int i,pre,k[1000001],nr,l,t,test;
void citire()
{
  FILE * pFile;
  long lSize;
  size_t result;

  pFile = fopen ( "prefix.in" , "rb" );

  // obtain file size:
  fseek (pFile , 0 , SEEK_END);
  lSize = ftell (pFile);
  rewind (pFile);

  // allocate memory to contain the whole file:
  fileData = (char*) malloc (sizeof(char)*lSize);

  // copy the file into the buffer:
  result = fread (fileData,1,lSize,pFile);
  endOfFile = fileData + lSize;

  /* the whole file is now loaded in the memory buffer. */

  // terminate
  fclose (pFile);
}

int main()
{
    citire();
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d\n",&t);
    char* pos = fileData;
    while(!('a'<=*pos&&*pos<='z') && pos < endOfFile)
    {
        pos++;
    }
    for(test=1;test<=t;test++)
    {
        //scanf("%s\n",&A);
        A = pos;
        int sol = 0;
        int n=1;
        //printf("%d ", k[0]);
        for(i=1;A[i]!='\n';i++)
        {
            n++;
            pre=k[i-1];
            while(A[pre]!=A[i]&&pre>0)
            {
                pre=k[pre-1];
            }
            if(A[i]!=A[pre])
                k[i]=0;
            else
                k[i]=pre+1;
            if ((i + 1) - k[i] <= k[i]) {
                sol = i + 1;
            }
            //printf("%d ", k[i]);
        }
        pos=pos+i+1;
        while(!('a'<=*pos&&*pos<='z') && pos < endOfFile)
        {
            pos++;
        }
        //printf("%d\n",nr*l);
        printf("%d\n", sol);
    }
    free(fileData);
    return 0;
}