Problema B - Porto de Leixões

No porto de Leixões, os contentores que aguardam embarque estão empilhados uns em cima dos outros, de modo a poupar espaço. No entanto, quando são empilhados, não o devem ser de qualquer maneira, pois o tempo que demora a carregar um navio depende da posição que ocupam nas pilhas os contentores que esse navio deve transportar. De facto, o tempo necessário é maior quando os contentores não estão no topo da pilha, pois nesse caso só podem ser manobrados depois de os contentores que estão por cima deles serem retirados.

Para aumentar a produtividade, a administração do porto está a preparar um plano de diminuição do tempo necessário para carregar os navios. De acordo com este plano, cada navio deve ser carregado acedendo apenas a contentores que estão no topo das pilhas. Por outro lado, o número de pilhas necessárias deve ser minimizado.

Neste problema, conhecemos a ordem pela qual os navios devem ser carregados e a ordem pela qual os contentores chegam. Cada navio é representado por uma letra maiúscula entre A e Z (inclusive) e os navios serão carregados por ordem alfabética. Cada contentor é etiquetado com a letra que representa o navio que o irá transportar. O número de contentores em cada pilha é ilimitado.

O Problema

Input

O input contém vários casos de teste. Cada um deles consiste numa única linha contendo entre 1 e 1000000 (inclusive) letras maiúsculas, representando a ordem de chegada dos contentores. Por exemplo, a linha ABAC significa que o primeiro contentor a chegar deve ir para o navio A, o segundo para o navio B, o terceiro para o navio A e o quarto para o navio C. Depois de todos os contentores terem chegado, os navios são carregados por ordem: primeiro o navio A, depois o navio B e assim por diante.

O fim dos testes é assinalado por uma linha contendo apenas a palavra "fim".

Output

O output é constituído por uma linha para cada caso de input, contendo o número de ordem do caso (na forma "Caso NUM:") seguido do número mínimo de pilhas de contentores necessárias para armazenar todos os contentores até começar o embarque. Espreite o exemplo para perceber a formatação do output.

Exemplo de Input

CCBAA
ABCABCABC
DF
fim

Exemplo de Output

Caso 1: 1
Caso 2: 3
Caso 3: 2