1#include <iostream>
 2#include <cstdio>
 3#include <cstring>
 4#include <algorithm>
 5typedef long long LL;
 6#define ri register int
 7using namespace std;
 8#define MAXALP 30
 9#define ms(a,x) memset(a,x,sizeof(a)) 
10const int N = 3E5+7;
11struct PAM
12{
13    int cnt,len,fail;
14    int nxt[MAXALP];
15}st[N];
16int n, m, sz , last, cur;
17char s[N];
18inline int new_node(int x)
19{
20    st[sz].len = x; st[sz].cnt = 0;
21    ms(st[sz].nxt,0);
22    return sz++;
23}
24inline int get_fail(int x, int n)
25{
26    while(s[n-st[x].len-1] != s[n]) x = st[x].fail;
27    return x;
28}
29inline void pam_init()
30{
31    sz = 0 ;
32    new_node(0);
33    new_node(-1);
34    st[0].fail = 1;
35    ms(st[0].nxt,0);
36    last = 0;
37}
38void pam_insert( int c,int head)
39{
40    cur = get_fail(last,head);
41    if (!st[cur].nxt[c])
42    {
43    int nw = new_node(st[cur].len+2);
44    st[nw].fail = st[get_fail(st[cur].fail,head)].nxt[c];
45    st[cur].nxt[c] = nw;
46    }
47    last = st[cur].nxt[c];
48    st[last].cnt++;
49}
50int main()
51{
52//  freopen("./in.txt","r",stdin);
53    int T;
54    int cas = 0 ;
55    cin>>T;
56    while (T--)
57    {
58        scanf("%s",s);
59        n = strlen(s);
60        pam_init();
61        for(int i=0;i<n;i++) pam_insert(s[i]-'a',i);
62        printf("Case #%d: %d\n",++cas,sz-2);
63    }
64
65    return 0;
66}

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年11月14日 星期二 00时13分44秒
 4File Name :103.cpp
 5************************************************ */
 6
 7#include <bits/stdc++.h>
 8#define ms(a,x) memset(a,x,sizeof(a))
 9typedef long long LL;
10using namespace std;
11const int N=3E5+7;
12struct PAM
13{
14    int fail,cnt,len;
15    int nxt[26];
16}st[N];
17char S[N];
18int n,now,sz;
19void pam_init()
20{
21    ms(st,0);
22    st[0].fail = st[1].fail = 1;
23    st[1].len = -1;
24    sz = 1;
25}
26void extend(int c,int pos)
27{
28    int p = now;
29    while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
30    if (!st[p].nxt[c]){
31    int np=++sz,q=st[p].fail;
32    st[np].len=st[p].len+2;
33    while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
34    st[np].fail=st[q].nxt[c];
35    st[p].nxt[c] = np;
36    }
37    now=st[p].nxt[c];
38    st[now].cnt++;
39}
40int main()
41{
42    int T,cas=0;
43    cin>>T;
44    while (T--)
45    {
46        scanf("%s",S);
47        pam_init();
48        for ( int i = 0 ,_=strlen(S); i < _ ; i++)
49        extend(S[i]-'a',i);
50        printf("Case #%d: %d\n",++cas,sz-1);
51    }
52    return 0;
53}