对于一个字符串 s，在删除至多一个子串后，要求余下的部分构成回文串。

问余下部分的最长长度是多少。

注意，允许不进行删除。

本题有 T 组数据

数据范围： $1 \le T \le 10,\ |s| \le 10^5$

CODE：

#include <bits/stdc++.h>
using namespace std;
#define maxn (int)1e5 + 10
char s[maxn];
int d1[maxn], d2[maxn];
void calD(char s[], int n){
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        d1[i] = k--;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }
        d2[i] = k--;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
}
void doit(){
    scanf("%s", s + 1);
    int n = strlen(s) - 1;
    calD(s, n);
    int ans = -114514;
    for(int i = 1; i <= n; i++){
        if(d1[i] - i == 0 || d1[i] + i == n + 1) ans = max(ans, 2 * d1[i] - 1);
        if(d2[i] - i == 1 || d2[i] + i == n + 1) ans = max(ans, d2[i] * 2);
    }
    cout << ans << endl;
    return ;
}
int main(){
    int T;
    cin >> T;
    for(int i = 1; i <= T; i++) doit();
    return 0;
}

SAMPLE

input

2
aaa
abbab

output

3
4