https://www.luogu.com.cn/problem/P1723

#include <iostream>
//#include<bits/stdc++.h>
#include <string>
#include <cstring>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <deque>
#include <iomanip>
#include <queue>
#include <utility>
#include <unordered_map>
//#define x first
//#define y second
//#define int long long 
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
#define endl '\n'
#define buff ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
typedef unsigned long long ULL;
//priority_queue<int, vector<int>, less<int> >dg;
//priority_queue<int, vector<int>, greater<int> >xg;
//int dx[] = { -1,-1,-1,0,0,1,1,1 };
//int dy[] = { -1,0,1,-1,1,-1,0,1 };
//#define INF 0x3f3f3f3f
//ceil函数可以把x上取整。(加取整）(int)
//floor函数可以把x下取整。
//round函数可以把x四舍五入。
//数字分为整型与浮点型，则对应的函数是stoi（）、stod（）、stof（）等。
//unordered_map<long, long> mp;
//洛谷数组开得不够大报WA而不是RE

const int N = 22000010;
char s[N], str[N];
int dp[N], n;
int init() {
    int len = strlen(s);
    str[0] = '^';
    str[1] = '$';
    int j = 1;
    for (int i = 0; i < len; i++)
    {
        str[++j] = s[i];
        str[++j] = '$';
    }
    str[++j] = '&';
    return j;
}
int Manacher() {
    int n = init();
    int right = 1, pos = 1;
    int ret = -1;
    for (int i = 1; i < n; i++)
    {
        if (i < right) dp[i] = min(dp[2 * pos - i], right - i);
        else dp[i] = 1;
        while (str[i - dp[i]] == str[i + dp[i]]) dp[i]++;
        if (i + dp[i] > right) right = i + dp[i], pos = i;
        ret = max(ret, dp[i] - 1);
    }
    return ret;
}
void solve()
{
    int q;
    cin >> q;
    while (q--)
    {
        memset(dp, 0, sizeof(dp));
        cin >> s;
        printf("%d\n", Manacher());

    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}