#include <iostream>

#include <string>

#include <cstring>

#include <algorithm>

using namespace std;

int MANACHER(const string &str)

{

    string data;

    int len = str.length();

    data+="$#";

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

    {

        data+=str[i];

        data+='#';

    }

    data+='@';

    //到此预处理完成

    len = data.length();

    int *temp = new int[len+];

    memset(temp,,sizeof(temp));

    int MaxIndex=;

    int i=,index=,res=;

    for(;i<len;i++)

    {

        if (MaxIndex>i)

        {

            temp[i]=(MaxIndex-i<temp[*index-i]?MaxIndex-i:temp[*index-i]);

        }

        else

            temp[i]=;

        while (data[i-temp[i]] == data[i+temp[i]])

        {

            temp[i]++;

        }

        if(i+temp[i] > MaxIndex)

        {

            MaxIndex = i+temp[i];

            index=i;

        }

        res = (res>temp[i]?res:temp[i]);

    }

    delete[]temp;

    return res-;

}

int main()

{

    string str ;

    int n;

    while(cin >> n)

    {

        while (n--)

        {

            cin >> str;

            cout << MANACHER(str)<<endl;

        }

    }

    return ;

}