#include <cstdio>

 #include <cstring>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define N 20010

 int n, aa[N];

 int sa[N], rk[N], ht[N], vv[N];

 void expand( int *s, int *r, int *sa, int *rk, int k ) {

     for( int i=; i<=n; i++ )

         vv[r[s[i]]]=i;

     for( int i=n; i>=; i-- )

         if( s[i]>k ) sa[vv[r[s[i]-k]]--] = s[i]-k;

     for( int i=n-k+; i<=n; i++ )

         sa[vv[r[i]]--] = i;

     for( int i=; i<=n; i++ )

         rk[sa[i]] = rk[sa[i-]]+(r[sa[i]]!=r[sa[i-]]||r[sa[i]+k]!=r[sa[i-]+k]);

 }

 void calcht() {

     for( int i=,k=; i<=n; i++ ) {

         if( rk[i]== ) {

             k = ht[i] = ;

             continue;

         }

         int j=sa[rk[i]-];

         while( aa[i+k]==aa[j+k] ) k++;

         ht[i] = k;

         if( k> ) k--;

     }

 }

 void suffix() {

     static int tsa[N], trk[N];

     for( int i=; i<=; i++ ) vv[i] = ;

     for( int i=; i<=n; i++ ) vv[aa[i]]++;

     for( int i=; i<=; i++ ) vv[i]+=vv[i-];

     for( int i=n; i>=; i-- ) sa[vv[aa[i]]--]=i;

     for( int i=; i<=n; i++ )

         rk[sa[i]] = rk[sa[i-]]+(aa[sa[i]]!=aa[sa[i-]]);

     for( int k=; k<n; k<<= ) {

         expand( sa, rk, tsa, trk, k );

         for( int i=; i<=n; i++ )

             sa[i]=tsa[i], rk[i]=trk[i];

     }

     calcht();

 }

 int sov() {

     int nn = (n+)>>;

     for( int i=; i<=n; i++ )

         if( n-sa[i]+>=nn ) {

             int rt = sa[i];

             for( int j=i+; j<=n && ht[sa[j]]>=nn; j++ )

                 rt = min( rt, sa[j] );

             return rt;

         }

     return -;

 }

 int main() {

     int T;

     scanf( "%d", &T );

     while( T-- ) {

         static char buf[N];

         scanf( "%s", buf+ );

         n = strlen( buf+ );

         for( int i=; i<=n; i++ )

             aa[i+n] = aa[i] = buf[i]-'a'+;

         n += n;

         suffix();

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

     }

 }