#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
using namespace std;

const int MAX = 1000;

string table[MAX][MAX];

string intToStr(int v)
{
	string ans = "";
	while (v > 0) {
		ans = (char)('0'+v%10) + ans;
		v /= 10;
	}
	return ans;
}

int numLength(int a)
{
	if (a < 10)
		return 1;
	if (a < 100)
		return 2;
	return 3;
}

int checkForInc(int val)
{
	return (val == 9 || val == 99);
}
		
int main()
{
	int icase=0;
	string s;
	cin >> s;
	while (s != "0") {
		icase++;
		int len = s.length();
										// substrings of length < 2 can't be improved
		for(int i=0; i<len; i++)
			table[i][i] = s.substr(i,1);
		for(int i=0; i<len-1; i++) {
			if (s[i] == s[i+1]) 
				table[i][i+1] = "2" + s.substr(i,1);
			else
				table[i][i+1] = s.substr(i,2);
		}

		string stmp;
		for(int j=2; j<len; j++) {
			for(int i=0; i<len-j; i++) {
				int best = MAX+1;
				for(int k=0; k<j; k++) {
//if (j >= len-2) cout << "current best = " << best << ',' << table[i][i+j] << ", now concating " << table[i][i+k] << " with " << table[i+k+1][i+j] << endl;
					string s1 = table[i][i+k];
					string s2 = table[i+k+1][i+j];
					int len1 = s1.length();
					int len2 = s2.length();
					if (len1 + len2 < best) {
						table[i][i+j] = s1 + s2;
						best = len1+len2;
					}
					int loc = s2.find(s1);
					if (loc == string::npos)
						continue;
					if (loc == 0) {
						if (len2 + 3 <= best) {
							table[i][i+j] = "2("+s1+")" + s2.substr(len1);
							best = len2+3;
						}
						else if (len1 == 2 && s2.find(s1,2) == 2 && len2 + 1 <= best) {  // special case
							table[i][i+j] = "3("+s1+")" + s2.substr(4);
							best = len2+1;
						}

						continue;
					}
					int count = atoi(s2.c_str());
					if (count == 0)
						continue;
					int countLen = numLength(count);
					int lenInc = checkForInc(count);
					if (len1 == 1 && loc == countLen) {
						if (len2 + lenInc <= best) {
							table[i][i+j] = intToStr(count+1) + s2.substr(loc);
							best = len2 + lenInc;
						}
					}
					else if (len1 > 1 && loc == countLen+1 && s2[countLen] == '(' && countLen+len1+1 < len2 && s2[countLen+len1+1] == ')') {
						if (len2 + lenInc <= best) {
							table[i][i+j] = intToStr(count+1) + s2.substr(loc-1);
							best = len2 + lenInc;
						}
					}
				}
//cout << i << " to " << i+j << ": string " << s.substr(i, j+1) << " stored as " << table[i][i+j] << endl;
			}
		}
		cout << "Case " << icase << ": " << table[0][len-1].length() <<endl;// ' ' << table[0][len-1] << endl;

		cin >> s;
	}
}