#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<int(n);++i)
#define out(x) cerr<<#x"="<<x<<endl
typedef long long LL;
char s[112345];
int pre[112345];
int main(){
    int T;
    scanf("%d",&T);
    REP(tt,T){
        scanf("%s", s);
        int L=strlen(s);
        for(char *p=s; *p; ++p)
            *p=*p=='a'?-1:1;
        pre[0]=1;
        REP(i,L)pre[i+1]=pre[i]+s[i];
        int ans=abs(pre[L]);
        if(pre[L]>0){
            REP(i,L)pre[i+1]-=pre[L];
        }
        //REP(i,L+1)printf("%d%c",pre[i]," \n"[i==L]);
        map<int, int> cnt;
        LL tot=0;
        int num=0;
        REP(i,L)if(pre[i+1]>0 && s[i]==1){
            cnt[pre[i+1]]++;
            tot+=pre[i+1];
            ++num;
        }
        int lst=0;
        for(auto x: cnt){
            if(num>2){
                tot-=(num-2)*LL(x.first-lst);
                lst=x.first;
                num-=x.second;
            } else break;
        }
        ans+=tot;
        printf("Case %d: %d\n", tt+1, ans);
    }
}