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;