#include<bits/stdc++.h>
using namespace std;
int t,n,a[1000001],dp[10001][10001];
char s[1000001];
void solve(int t){
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-48;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++) dp[i][i]=a[i],dp[i][i-1]=dp[i+1][i]=0;
    for(int k=2;k<=n;k++){
        for(int l=1,r=k;r<=n;l++,r++){
            for(int i=l;i<=r;i++) dp[l][r]=min(dp[l][r],max(dp[l][i-1],dp[i+1][r])+a[i]);
        }
    }
    printf("Case #%d: %d\n",t,dp[1][n]);
}
int main(){
	scanf("%d",&t);
    for(int i=1;i<=t;i++) solve(i);
    return 0;
}
// dp[l][r]表示确定x在[l,r]中的最小代价