算法的核心就在这一句上了：p[i] = min(p[2*id-i], p[id] + id - i);

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <map>

#include <set>

#include <iomanip>

using namespace std;

const int N=;

/*int len;            //原串长

char str[N];        //接收原来的串

char s[N*2];        //做了插入处理的结果串

int P[N*2];         //保存关于长度的信息（回文长度的一半再加1）

int cal()

{

    int id=1, mx=1, max1=1;

    P[0]=1;

    P[1]=1;

    for(int i=2; s[i]!='\0'; i++)        //考虑以i为中心的回文串

    {

        P[i] =i>mx? 1: min( P[2*id-i],mx-i);

        while(s[i+P[i]]==s[i-P[i]])     //在这比对

            P[i]++;

        if(i+P[i]>mx)       //更新id和mx的位置

        {

            id=i;

            mx=i+P[i];

        }

        if(P[i]-1>max1)     //更新最大值

            max1=P[i]-1;

    }

    return max1;

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        scanf("%s",str);

        len=strlen(str);

        memset(s,0,sizeof(s));

        memset(P,0,sizeof(P));

        

        //插入符号#

        s[0]='$';

        s[1]='#';

        int i=0, j=2;

        for(; i<len; i++)

        {

            s[j++]=str[i];

            s[j++]='#';

        }

        cout<<cal()<<endl;

    }

    return 0;

}

*/

int Manacher(string &str, int len)

{

    //插上辅助字符#

    string tmp(len*+,'#');

    tmp[]='$';

    for(int i=; i<str.size(); i++)    tmp[i*+]=str[i];

    

    int ans=;

    int mx=, id=;

    vector<int> P(*len+,);

    

    for(int i=; i<tmp.size(); i++)

    {

        P[i]=( i>=mx? : min( P[*id-i], mx-i ));

        while( tmp[i-P[i]]==tmp[i+P[i]] )    P[i]++;    //匹配了就继续扩大P[i]

        

        if(mx<=i+P[i])//重要：更新位置

        {

            mx=i+P[i];

            id=i;

        }

        ans=max(ans, P[i]-); //这就是长度了，不信动手画。

    }

    return ans;

}

int main()

{

    int t;

    string str;

    cin>>t;

    while(t--)

    {

        cin>>str;

        cout<<Manacher(str, str.size())<<endl;;

    }

    return ;

}