#include<bits/stdc++.h>
using namespace std;
#define Mx 150
int dp[Mx][Mx];
string s;
set<string>paths;
int rec(int l,int r)
{
    if(l>=r)return 0;
    int &ret = dp[l][r];
    if(ret!=-1)return ret;
    ret = 111111111;
    if(s[l]==s[r])
    {
        ret = rec(l+1,r-1);
    }
    ret = min(ret,1+rec(l,r-1));
    ret = min(ret,1+rec(l+1,r));
    return ret;
}

void getPaths(int l,int r,string &res)
{
    if(l>r)
    {
        return ;
    }
    vector<pair<int,pair<int,int>>>V;
    if(s[l]==s[r])
    {
        V.push_back({rec(l+1,r-1),{s[l],0}});
    }
    V.push_back({1+rec(l,r-1),{s[r],1}});
    V.push_back({1+rec(l+1,r),{s[l],2}});
    sort(V.begin(),V.end());
    char curChar = V[0].second.first;
    int mv = V[0].second.second;
    res+=curChar;
    if(mv==0)getPaths(l+1,r-1,res);
    else if(mv==1)getPaths(l,r-1,res);
    else getPaths(l+1,r,res);
}
bool pal(string &x,int l,int r)
{
    return l>=r || pal(x,l+1,r-1);
}
int main()
{
    int kase,ks=1;
    freopen("in_pal.txt","r",stdin);
    freopen("out_pal.txt","w",stdout);
    cin >> kase;
    while(kase--)
    {
        cin >> s;
        string cachex = s;
        memset(dp,-1,sizeof dp);
        cout << "Case " << ks << ": " << rec(0,s.length()-1) << " ";
        //paths.clear();
        string result = "";
        getPaths(0,s.length()-1,result);
        cout << result;
        string finalResult = result;
        int st;
        if((s.length()+ rec(0,s.length()-1))&1)
        {
            st = result.length()-2;
        }
        else st = result.length()-1;

        for(int i=st; i>=0; i--){
            finalResult+=result[i];
            cout << result[i];
        }
        cout << endl;
        ks++;
        assert(pal(finalResult,0,finalResult.length()-1)==true);
        //cout << st << " " << result<< endl;
        //cout << "=>" << cachex << "<=" << endl;
    }
    return 0;
}