// Tom Wexler

import java.util.*;
import java.io.*;

public class B {
    public static void main(String[] args) {
        
        Scanner input = new Scanner(System.in);
        String str = input.next();
        int caseNo = 1;
        while (str.charAt(0) != '0') {
            int n = str.length();
            int[][] A = new int[n+1][n+1];
            String[][] Sol = new String[n+1][n+1];
            for(int i = 0; i < n; i++) {
                A[i][i+1] = 1;
                Sol[i][i+1] = ""+str.charAt(i);
            }
            for(int l = 2; l <= n; l++) {
                for(int start = 0; start <= n-l; start++) {
                    int end = start+l;
                    int best = l;
                    String bestStr = str.substring(start, end);
                    // check for concat
                    for(int mid = start+1; mid < end; mid++) {
                        if (A[start][mid]+A[mid][end] < best) {
                            best = A[start][mid]+A[mid][end];
                            bestStr = Sol[start][mid]+Sol[mid][end];
                        }
                    }
                    // check for rep
                    for(int reps = 2; reps <= l; reps++) {
                        if (l%reps == 0) {
                            int inc = l/reps;
                            boolean valid = true;
                            int i = start;
                            while(valid && i+inc < end) {
                                if (str.charAt(i) != str.charAt(i+inc)) valid = false;
                                i++;
                            }
                            if (valid) {
                                if (inc == 1 && A[start][start+inc]+(""+reps).length() < best) {
                                    best = A[start][start+inc]+(""+reps).length();
                                    bestStr = reps+""+Sol[start][start+inc];
                                }
                                else if (A[start][start+inc]+2+(""+reps).length() < best) {
                                    best = A[start][start+inc]+2+(""+reps).length();
                                    bestStr = reps+"("+Sol[start][start+inc]+")";
                                }
                            }
                        }
                    }
                    A[start][end]=best;
                    Sol[start][end]=bestStr;
                }
            }
            System.out.println("Case "+caseNo+": "+A[0][n]);//+" "+Sol[0][n]);
            
            str = input.next();
            caseNo++;
        }
    }
}