#include <iostream>

 #include <vector>

 #include <algorithm>

 #include <string>

 #include <string.h>

 #include <stdio.h>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #include <cmath>

 #include <ctime>

 #include <cassert>

 #include <sstream>

 using namespace std;

 const int N=*;

 char s[N];

 struct SuffixArray {

      int wa[N], wb[N], cnt[N], wv[N];

     int rk[N], height[N];

     int sa[N];

     bool cmp(int r[], int a, int b, int l) {

         return r[a] == r[b] && r[a+l] == r[b+l];

     }

     void calcSA(char r[], int n, int m) {

         int i, j, p, *x = wa, *y = wb;

         for (i = ; i < m; ++i) cnt[i] = ;

         for (i = ; i < n; ++i) cnt[x[i]=r[i]]++;

         for (i = ; i < m; ++i) cnt[i] += cnt[i-];

         for (i = n-; i >= ; --i) sa[--cnt[x[i]]] = i;

         for (j = , p = ; p < n; j *= , m = p) {

             for (p = , i = n - j; i < n; ++i) y[p++] = i;

             for (i = ; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

             for (i = ; i < n; ++i) wv[i] = x[y[i]];

             for (i = ; i < m; ++i) cnt[i] = ;

             for (i = ; i < n; ++i) cnt[wv[i]]++;

             for (i = ; i < m; ++i) cnt[i] += cnt[i-];

             for (i = n-; i >= ; --i) sa[--cnt[wv[i]]] = y[i];

             for (swap(x, y), p = , x[sa[]] = , i = ; i < n; ++i)

                 x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p- : p++;

         }

     }

     void calcHeight(char r[], int n) {

         int i, j, k = ;

         for (i = ; i <= n; ++i) rk[sa[i]] = i;

         for (i = ; i < n; height[rk[i++]] = k)

             for (k?k--:, j = sa[rk[i]-]; r[i+k] == r[j+k]; k++);

     }

     int lcp(int a,int b,int len) {

         if (a==b) return len-a;

         int ra=rk[a],rb=rk[b];

         if (ra>rb) swap(ra,rb);

         return queryST(ra+,rb);

     }

     int st[N][];

     void initST(int n) {

         for (int i=; i<=n; i++)

             st[i][]=height[i];

         for (int j=; (<<j)<=n; j++) {

             int k=<<(j-);

             for (int i=; i+k<=n; i++)

                 st[i][j]=min(st[i][j-],st[i+k][j-]);

         }

     }

     int queryST(int a,int b) {

         if (a>b) swap(a,b);

         int dis=b-a+;

         int k=log((double)dis)/log(2.0);

         return min(st[a][k],st[b-(<<k)+][k]);

     }

     void solve(int cas) {

         int n=strlen(s);

         s[n]='#';

         for (int i=;i<n;i++) {

             s[n++i]=s[n--i];

         }

         int o=n;

         n=*n+;

         s[n]='\0';

         calcSA(s,n+,);

         calcHeight(s,n);

         initST(n);

         long long ret=;

         int curLcp=;

         for (int i=;i<=n;i++) { //odd

             int pos=sa[i];

             curLcp=min(curLcp,height[i]);

             if (pos<o) {

                 int ops=n--pos;

                 int now=lcp(pos,ops,n);

                 ret+=max(,now-curLcp);

                 if (now>=curLcp)

                     curLcp=now;

             }

         }

         curLcp=;

         for (int i=;i<=n;i++) { //even

             int pos=sa[i];

             curLcp=min(curLcp,height[i]);

             if (pos<o) {

                 int ops=n-pos;

                 int now=lcp(pos,ops,n);

                 ret+=max(,now-curLcp);

                 if (now>=curLcp)

                     curLcp=now;

             }

         }

         printf("Case #%d: %I64d\n",cas,ret);

     }

 }suf;

 int main () {

     //freopen("out.txt","r",stdin);

     int T;

     scanf("%d",&T);

     int cas=;

     while (T--) {

        scanf("%s",s);

        suf.solve(cas);

        cas++;

     }

     return ;

 }