#include <bits/stdc++.h>

using namespace std;

bool table[][] = {false};

string longestPalindromeDP(string s)

{

    int n = s.length();

    int longestBegin = ;

    int maxLen = ;

    memset(table,,sizeof(table));

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

        table[i][i] = true;   //前期的初始化

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

    {

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

        {

            int j = i+len-;

            if (s[i] == s[j] && table[i+][j-])

            {

                table[i][j] = true;

                longestBegin = i;

                maxLen = len;

            }

        }

    }

    return s.substr(longestBegin, maxLen);

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        string str;

        cin>>str;

        string ans = longestPalindromeDP(str);

        cout<<ans.length()<<endl;

    }

    return ;

}

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

char instr[maxn],str[maxn*];

int rad[maxn*];

int Manacher()

{

    int i,j,maxx;

    int n = strlen(instr);

    memset(str,'#',sizeof(str));

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

        str[(i+)<<] = instr[i];

    n = (n+)<<;

    str[n] = '$';

    int maxRad;

    maxRad = j = maxx = ;

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

    {

        if(i<maxx)

            rad[i] = min(rad[*j-i],maxx-i);

        else rad[i] = ;

        while(str[i-rad[i]]==str[i+rad[i]])

            rad[i] ++;

        if(maxRad<rad[i])

            maxRad = rad[i];

        if(rad[i]+i>maxx)

        {

            j = i;

            maxx = rad[i] + i;

        }

    }

    return maxRad;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",instr);

        printf("%d\n",Manacher()-);

    }

    return ;

}