#include<string.h>

 #include<stdio.h>

 #include<iostream>

 #define N 1000005

 using namespace std;

 int Next[N],tlen;

 char T[N];

 void getNext()

 {

      int j, k;

     j = ; k = -; Next[] = -;

     while(j < tlen)

     {

         if(k == - || T[j] == T[k])

             Next[++j] = ++k;

         else

             k = Next[k];

     }

 }

 int main()

 {

     int cas,min;

     scanf("%d",&cas);

     while(cas--)

     {

         scanf("%s",T);

         tlen=strlen(T);

         getNext();

         min=tlen-Next[tlen];

         if(min==tlen)

             printf("%d\n",tlen);

         else if(tlen%min==)

             printf("0\n");

         else

             printf("%d\n",min-tlen%min);

     }

     return ;

 }