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

const int MAX = 1000;

int table[MAX][MAX];

int numLength(int a)
{
	if (a < 10)
		return 1;
	if (a < 100)
		return 2;
	return 3;
}
	
int main()
{
	int icase=0;
	string s;
	cin >> s;
	while (s != "0") {
		icase++;
		int len = s.length();
		for(int i=0; i<len; i++) {
			table[i][i] = 1;
		}
		for(int i=0; i<len-1; i++) {
			table[i][i+1] = 2;
		}
		for(int j=2; j<len; j++) {
			for(int i=0; i<len-j; i++) {
				table[i][i+j] = j+1;
				for(int k=0; k<j; k++) { // Check for concatenation
					int newsol = table[i][i+k] + table[i+k+1][i+j];
					if (newsol < table[i][i+j]) table[i][i+j] = newsol;
				}
				for(int k=1; k < j;k++) { // Check for repetition of length k
					if ((j+1)%k == 0) { // Don't bother checking if the substring length isn't divisible by k
						bool valid = true;
						for(int l=0; l<=j-k; l++) { // Make sure each character matchs the one k away
							if (s[i+l] != s[i+l+k]) {
								valid = false;
								break;
							}
						}
						if (valid && k > 1) { // Repetition of a multi character string (parens)
							int newsol = numLength((j+1)/k) + 2 + table[i][i+k-1];
							if (newsol < table[i][i+j]) table[i][i+j] = newsol;
						}
						if (valid && k == 1) { // Repetition of a single character string (no parens)
							int newsol = numLength((j+1)/k) + table[i][i+k-1];
							if (newsol < table[i][i+j]) table[i][i+j] = newsol;
						}
					}
				}
			}
		}
		cout << "Case " << icase << ": " << table[0][len-1] << endl;

		cin >> s;
	}
}