#include <cstdio>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cmath>

#include <cstring>

#include <stack>

#include <set>

#include <map>

#include <vector>

using namespace std;

#define INF 0x2fffffff

#define LL long long

#define MAX(a,b) ((a)>(b))?(a):(b)

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

char a[1000005];

char b[2000005];

int  p[2000005];

int newstring(){

    b[0] = '$';

    b[1] = '#';

    int len = strlen(a);

    int j = 2;

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

        b[j] = a[i];

        b[++j] = '#';

        ++j;

    }

    b[j] = '\0';

}

int manachar(){

    int len = strlen(b);

    int id = 0;

    int maxd = 1;

    int ans = 0;

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

        if(maxd > i){

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

        }else{

            p[i] = 1;

        }

        while(b[p[i]+i] == b[i-p[i]])

            p[i]++;

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

            maxd = p[i]+i;

            id = i;

        }

        if(ans < p[i]){

            ans = p[i];

        }

    }

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

}

int main(){

    int t;

    cin >> t;

    while(t--){

        scanf("%s",a);

        newstring();

        manachar();

    }

    return 0;

}

依据回文串左右是全然同样的性质。左边求出来后非常快的就能求出来右边的长度