#include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <cctype>

 #include <algorithm>

 #include <queue>

 #include <deque>

 #include <queue>

 #include <list>

 #include <map>

 #include <set>

 #include <vector>

 #include <utility>

 #include <functional>

 #include <fstream>

 #include <iomanip>

 #include <sstream>

 #include <numeric>

 #include <cassert>

 #include <ctime>

 #include <iterator>

 const int INF = 0x3f3f3f3f;

 const int dir[][] = {{-,},{,},{,-},{,},{-,-},{-,},{,-},{,}};

 using namespace std;

 char a[];

 int dp[][];

 const int MOD = ;

 int main(void)

 {

     #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     ios::sync_with_stdio(false);

     int t; cin>>t;

     for (int k = ; k <= t; ++k)

     {

         cin>>a; int len = strlen(a);

         memset(dp, , sizeof(dp));

         for (int i = ; i < len; ++i) for (int j = ; j < len; ++j)

             if (i==j) dp[i][j] = ;

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

         {

             for (int j = ; i+j < len; ++j)

             {

                 if (a[i+j] == a[j])

                 {

                     dp[j][i+j] = dp[j][i+j-] + dp[j+][i+j] + ;

                 }

                 else

                 {

                     dp[j][i+j] = dp[j+][i+j] + dp[j][i+j-] - dp[j+][i+j-];

                 }

                 dp[j][i+j] = (dp[j][i+j] + MOD)%MOD;

             }

         }

         cout<< "Case "<<k<< ": "<<dp[][len-]<<endl;

     }

     return ;

 }

 /*

     模拟一下第二个样例 aaaaa 就懂了

 */