Khaled was sitting in the garden under an apple tree, suddenly! , well... you should guess what happened, an apple fell on his head! , so he came up with a new Cryptography method!!
The method deals only with numbers, so... If you want to encode a number, you must represent each of its digits with a set of strings, then the size of the set is the digit itself, No set should contain the same string more than once.
For example: the number 42, can be represented with the following two sets:
1) "dog" "load" "under" "nice".
2) "stack" "dog".
The first set contain four strings so it represent the digit 4.
The second set contain two strings so it represent the digit 2.
Given N strings, what is the smallest number you can get from dividing these strings into non-empty sets, and then decode the result by Khaled's Cryptography method? , You must use all the given strings, and no set should contain the same string more than once.
The input consists of several test cases, each test case starts with 0 < N ≤ 10000, the number of the given strings, then follows N space-separated string, each string will contain only lower-case English letters, and the length of each string will not exceeded 100.
You can assume that there are no more than nine distinct strings among the given strings.
A line containing the number 0 defines the end of the input you should not process this line.
For each test case print a single line in the following format: "Case c: x" where c is the test case number starting from 1 and x is the solution to the described problem above.
In the first sample, we divided the given strings into two sets, the first set contains two word: "one" and "two" so it represents the digit 2, the second set contains only one word: "two" so it represent the digit 1.
## Input
The input consists of several test cases, each test case starts with 0 < N ≤ 10000, the number of the given strings, then follows N space-separated string, each string will contain only lower-case English letters, and the length of each string will not exceeded 100.You can assume that there are no more than nine distinct strings among the given strings.A line containing the number 0 defines the end of the input you should not process this line.
## Output
For each test case print a single line in the following format: "Case c: x" where c is the test case number starting from 1 and x is the solution to the described problem above.
[samples]
## Note
In the first sample, we divided the given strings into two sets, the first set contains two word: "one" and "two" so it represents the digit 2, the second set contains only one word: "two" so it represent the digit 1.
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of given strings.
Let $ S = \{s_1, s_2, \dots, s_N\} $ be the multiset of strings.
Let $ D \subseteq S $ be the set of *distinct* strings, with $ |D| \leq 9 $.
Let $ f(d) $ denote the frequency of distinct string $ d \in D $ in $ S $.
A *valid partition* is a collection of non-empty, pairwise disjoint subsets $ \{P_1, P_2, \dots, P_m\} $ of $ S $ such that:
- $ \bigcup_{i=1}^m P_i = S $,
- Each $ P_i $ contains no duplicate strings (i.e., all elements in $ P_i $ are distinct),
- Each $ P_i $ corresponds to a digit $ d_i = |P_i| \in \{1, 2, \dots, 9\} $ (since $ |D| \leq 9 $, no set can have size > 9).
**Constraints**
1. $ 1 \leq N \leq 10000 $
2. Each string consists of lowercase English letters, length ≤ 100
3. $ |D| \leq 9 $
4. Each set $ P_i $ must have size $ \geq 1 $ and $ \leq 9 $
5. All $ N $ strings must be used exactly once.
**Objective**
Minimize the integer $ x $ formed by concatenating the digits $ d_1, d_2, \dots, d_m $ (in any order), where each $ d_i = |P_i| $, subject to the constraint that the multiset of frequencies $ \{f(d) \mid d \in D\} $ must be realizable by the partition $ \{P_1, \dots, P_m\} $.
That is, find the lexicographically smallest number $ x $ (as a decimal integer) that can be formed by partitioning the $ N $ strings into $ m \geq 1 $ non-empty sets, each of size $ \in \{1,2,\dots,9\} $, such that the total number of times each distinct string is used equals its frequency $ f(d) $.