#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;
}

string incrVal(string s)
{
	int val = atoi(s.c_str()) + 1;
	return intToStr(val);
}

int numReps(string s1, string s2)
{
	int len1 = s1.length();
	int len2 = s2.length();
	int count = 0;
	int j=0;
	while (j < len2 && s2.substr(j, len1) == s1) {
		count++;
		j += len1;
	}
	return count;
}

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

int check (string s1, string s2, string& s3)
{
	int len1 = s1.length();
	int len2 = s2.length();
	string s = s1+s2;						// start with simple concatenation
	int len = len1+len2;
	int best = len;
	s3 = s;
											// now check for prefix repetition
	for(int i=1; i<=s.length()/2; i++) {
		int count = numReps(s.substr(0,i), s.substr(i));
		if (count > 0) {
			string tmp;
			if (i == 1)
				tmp = intToStr(count+1) + s.substr(0,i) + s.substr(count+1);
			else
				tmp = intToStr(count+1) + '(' + s.substr(0,i) + ')' + s.substr(i*(count+1));
			if (tmp.length() <= best) {
				best = tmp.length();
				s3 = tmp;
			}
		}
	}
											// finally, see if we can add to an existing
											//   repetition
	int j=-1;
	while (true) {
		j++;
		while (j < s.length() && !isdigit(s[j]))
			j++;
		if (j == s.length())
			break;
		int k=j+1;
		while (isdigit(s[k]))
			k++;
		if (s[k] == '(') {					// repeated string length > 1
			if (s.substr(0,j) == s.substr(k+1,j) && (k+1+j < s.length() && s[k+1+j] == ')')) {
				int count = atoi(s.substr(j).c_str())+1;
				string tmp = intToStr(count) + s.substr(k);
				if (tmp.length() <= best) {
					best = tmp.length();
					s3 = tmp;
				}
			}
		}
											// repeated string length == 1 -
											//   only have to check if s1 length
											//   is 1
		else if (len1 == 1 && j == 1 && s1[0] == s[k]) {
			int count = atoi(s.substr(j).c_str())+1;
			string tmp = intToStr(count) + s.substr(k);
			if (tmp.length() <= best) {
				best = tmp.length();
				s3 = tmp;
			}
		}
	}
	return best;
}

int main()
{
	int icase=0;
	string s;
	cin >> s;
	while (s != "0") {
		icase++;
		int len = s.length();
										// substrings of length < 4 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 (check(table[i][i+k], table[i+k+1][i+j], stmp) < best) {
						table[i][i+j] = stmp;
						best = stmp.length();
					}
				}
//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() << ' ' << table[0][len-1] << endl;

		cin >> s;
	}
}