char s[maxn], ne[maxn];
int p[maxn];
int manacher(char *s) {
    int len = strlen(s), cnt = 0;
    ne[cnt++] = '~'; ne[cnt++] = '#';
    for(int i = 0; i < len; i++) {
        ne[cnt++] = s[i];
        ne[cnt++] = '#';
    }
    ne[cnt] = '\0';
    int id, mx = 0, res = 0;
    for(int i = 1; i < cnt; i++) {
        p[i] = i < mx?min(mx-i, p[2*id-i]):1;
        while(ne[i+p[i]] == ne[i-p[i]]) p[i]++;
        if(mx < p[i]+i) id = i, mx = p[i]+i;
        res = max(res, p[i]);
    }
    return res-1;
}