#include<cstdio>
#include<cstdlib>
using namespace std;
//char A[1000001];
char *A;
char* data;
int i,pre,k[1000001],nr,l,t,test;
char* citire()
{
  FILE * pFile;
  long lSize;
  char * buffer;
  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:
  buffer = (char*) malloc (sizeof(char)*lSize);

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

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

  // terminate
  fclose (pFile);
  return buffer;
}

int main()
{
    data=citire();
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d\n",&t);
    char* pos = data;
    while(!('a'<=*pos&&*pos<='z'))
    {
        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(2*k[i]==i+1)
            {
                l=(i+1)/2;
                nr=2;
            }
            else if(l!=0&&k[i]!=0&&k[i]%l==0&&(2*k[i]-i-1)%l==0&&k[i]*2>=i)
            {
                nr++;
            }*/
            if ((i + 1) - k[i] <= k[i] && (i + 1) % ((i + 1) - k[i]) == 0) {
                sol = i + 1;
            }
            //printf("%d ", k[i]);
        }
        pos=pos+i+1;
        while(!('a'<=*pos&&*pos<='z'))
        {
            pos++;
        }
        //printf("%d\n",nr*l);
        printf("%d\n", sol);
    }
    return 0;
}