#1032 : 最长回文子串

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <stack>

 #include <cctype>

 #include <vector>

 #include <cmath>

 #define ll long long

 using namespace std;

 const int M = ;

 const int N = ;

 const ll mod = ;

 int T;

 char te[N];

 char s[*N];

 int p[*N];

 int ans;

 int l;

 void pre()  //为了防止字符比较的时候越界，我在这个加了‘#’的字符串之前还加了另一个特殊字符‘$’，故我的新串下标是从1开始的

 {

     int l1=strlen(te);

     l=*l1+;

     s[]='$';

     s[]='#';

     for(int i=;i<l1;i++){

         s[i*+]=te[i];

         s[i*+]='#';

     }

     s[l]='\0';

 }

 void Manacher()

 {

     int i,mx,id;    //我们用mx记在i之前的回文串中，延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。

     mx=;

     for(i=;i<l;i++){

         if(mx>i){

             p[i]=min(p[*id-i],mx-i);

         }

         else{

             p[i]=;

         }

         for(;s[ i+p[i] ]==s[ i-p[i] ];p[i]++){

             if(i+p[i]>mx){

                 mx=i+p[i];

                 id=i;

             }

         }

     }

 }

 int main()

 {

     //freopen("data.in","r",stdin);

     scanf("%d",&T);

     for(int ccnt=;ccnt<=T;ccnt++){

     //while(scanf("%d%d",&a,&b) != EOF) {

         scanf("%s",te);

         pre();

         Manacher();

         int i;

         ans=;

         for(i=;i<l;i++){

             ans=max(ans,p[i]-);

         }

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

     }

     return ;

 }