struct pam{
    int S[maxn];
    int len[maxn], fail[maxn], last, n;
    int ch[maxn][30], cnt[maxn], tot, id[maxn];
    void init() {
        tot = 0;
        newnode(0);newnode(-1);last = 0;
        last = 0;n = 0;S[n] = -1;fail[0] = 1;
    }
    int newnode(int x) {
        len[tot] = x;
        cnt[tot] = fail[tot] = 0;
        for(int i = 0; i < 26; i++) ch[tot][i] = 0;
        return tot++;
    }
    int getfail(int x) {
        while(S[n] != S[n-len[x]-1]) x = fail[x];
        return x;
    }
    void insert(char *s) {
        int l = strlen(s);
        for(int i = 0; i < l; i++) {
            int c = s[i]-'a';
            S[++n] = c;
            int cur = getfail(last);
            if(!ch[cur][c]) {
                int now = newnode(len[cur]+2);
                fail[now] = ch[getfail(fail[cur])][c];
                ch[cur][c] = now;
            }
            last = ch[cur][c];cnt[last]++;id[last] = n;
        }
    }
    void count() {
        for(int i = tot-1; i >= 0; i--) cnt[fail[i]] += cnt[i];
    }
}pam;