UVA1062 Containers

一个集装箱码头，它接收从国内公路或铁路到达的集装箱，并将其装载至海船上。 这个集装箱码头可以看做几个栈的组合，当集装箱到达码头时，集装箱就会被放在某一个栈的栈顶。当海船到达时，海船就会从某一个栈的**栈顶**上装载集装箱。 如果一个不在栈顶的集装箱想要被装载，那么就必须移除上面的集装箱，而这会耽误装货时间。 解决这个问题的好办法就是：建造更多的栈，但这会占用地面空间。 你的任务就是给出一个方案，使得每艘海船到达时都可以**直接**从栈顶装载集装箱（也就是说，这艘船打算装载的集装箱必须在当前的栈顶，或者某个打算被装载的集装箱之上都是打算被装载到同一艘海船上的集装箱），且栈的数量尽可能少。 对于这个问题，我们知道： 1. 海船用一个大写字母编号，且严格按照字典序到达码头。 2. 每个集装箱都标有一个大写字母，代表这个集装箱应该被装载到那一艘海船上。 3. 栈可以无限高。

输入包含很多行，每一行代表一个测试用例。以 `end` 结束。 每一行有很多大写字母（不超过 $1000$ 个），代表集装箱的到达顺序。待集装箱**全部**到达以后，海船才会按顺序到达。

对于每一个测试用例，输出测试用例编号（从 $1$ 开始）和装载开始前所需要的栈的数量。 #### 4、输入样例 ``` A CBACBACBACBACBA CCCCBBBBAAAA ACMICPC end ``` #### 5、输出样例 ``` Case 1: 1 Case 2: 3 Case 3: 1 Case 4: 4 ```