const int maxn = 1e5, sigma = 26;
 
int s[maxn], len[maxn], link[maxn], to[maxn][sigma];
 
int n, last, sz;
 
void init()
{
    s[n++] = -1;
    link[0] = 1;
    len[1] = -1;
    sz = 2;
}
 
int get_link(int v)
{
    while(s[n - len[v] - 2] != s[n - 1]) v = link[v];
    return v;
}
 
void add_letter(int c)
{
    s[n++] = c;
    last = get_link(last);
    if(!to[last][c])
    {
        len [sz] = len[last] + 2;
        link[sz] = to[get_link(link[last])][c];
        to[last][c] = sz++;
    }
    last = to[last][c];
}

Y29uc3QgaW50IG1heG4gPSAxZTUsIHNpZ21hID0gMjY7CgppbnQgc1ttYXhuXSwgbGVuW21heG5dLCBsaW5rW21heG5dLCB0b1ttYXhuXVtzaWdtYV07CgppbnQgbiwgbGFzdCwgc3o7Cgp2b2lkIGluaXQoKQp7CiAgICBzW24rK10gPSAtMTsKICAgIGxpbmtbMF0gPSAxOwogICAgbGVuWzFdID0gLTE7CiAgICBzeiA9IDI7Cn0KCmludCBnZXRfbGluayhpbnQgdikKewogICAgd2hpbGUoc1tuIC0gbGVuW3ZdIC0gMl0gIT0gc1tuIC0gMV0pIHYgPSBsaW5rW3ZdOwogICAgcmV0dXJuIHY7Cn0KCnZvaWQgYWRkX2xldHRlcihpbnQgYykKewogICAgc1tuKytdID0gYzsKICAgIGxhc3QgPSBnZXRfbGluayhsYXN0KTsKICAgIGlmKCF0b1tsYXN0XVtjXSkKICAgIHsKICAgICAgICBsZW4gW3N6XSA9IGxlbltsYXN0XSArIDI7CiAgICAgICAgbGlua1tzel0gPSB0b1tnZXRfbGluayhsaW5rW2xhc3RdKV1bY107CiAgICAgICAgdG9bbGFzdF1bY10gPSBzeisrOwogICAgfQogICAgbGFzdCA9IHRvW2xhc3RdW2NdOwp9