A linguist, Nodvic Natharus Damenhof (commonly called *Dr. Usoperant*), invented an artificial language *Usoperant* in 2007. The word *usoperant* means eone which tiresf. Damenhoffs goal was to create a complex and
pedantic language that would remind many difficulties in universal communications. Talking in Usoperant, you
should remember the importance of choosing your words in many conversations.

For example of the complexity, you may be confused by the way to say large numbers. Usoperant has some
words that indicate exponential numbers in decimal, described as 10^{p} where *p* is a positive integer. In terms of
English, those words might include thousand for 10^{3} (1,000), million for 10^{6} (1,000,000), and *undecillion* for
10^{36} (1,000,000,000,000,000,000,000,000,000,000,000,000).

You can concatinate those words to express larger numbers. When two words *w*_{1} and *w*_{2} mean numbers 10^{p1}
and 10^{p2} respectively, a concatinated word *w*_{1}*w*_{2} means 10^{p1+p2}. Using the above examples in English (actually
the following examples are incorrect in English), you can say 10^{9} by *millionthousand*, 10^{12} by *millionmillion*
and 10^{39} by *undecillionthousand*. Note that there can be multiple different expressions for a certain number.
For example, 10^{9} can also be expressed by *thousandthousandthousand*. It is also possible to insert separators
between the adjacent components like *million-thousand* and *thousand-thousand-thousand*.

In this problem, you are given a few of such words, their representing digits and an expression of a certain number in Usoperant. Your task is to write a program to calculate the length of the shortest expression which represents the same number as the given expression.

The expressions in the input do not contain any separators like *millionthousand*. In case of ambiguity, the
expressions should be interpreted as the largest number among possibles. The resultant expressions should
always contain separators like *million-thousand*, so we can distinguish, for example, *x*-*x* (a concatinated word of
two *x*'s) and *xx* (just a single word). The separators should not be counted in the length.

The input consists of multiple test cases. Each test case begins with a line including an integer *N* (1 ≤ *N* ≤ 100).
The integer *N* indicates the number of words in the dictionary of exponential numbers.

The following *N* lines give the words in the dictionary. Each line contains a word *w _{i}* and an integer

Then a line which contains an expression of a number in Usoperant follows. The expression consists of at most 200 alphabetical letters.

The end of the input is indicated by a line which contains only a single 0.

For each test case, print a line which contains the case number and the length of the shortest expression which represents the same number as the given expression in the input.

3 billion 9 million 6 thousand 3 billionmillionthousand 3 oku 8 sen 3 man 4 okusenman 2 nico 2 video 4 niconicovideo 6 abcd 1 efgh 2 abcde 4 fgh 6 y 8 yy 10 abcdefgh 0

Case 1: 14 Case 2: 9 Case 3: 10 Case 4: 2

In the fourth case, the word *abcdefgh* can be separated as *abcd-efgh* (representing 10^{3} ) and *abcde-fgh*
(representing 10^{10} ), and by the rule described in the problem statement, this word should be interpreted as 10^{10}.
As this number can be expressed by *yy*, the length of the shortest expression is two (as in the sample output). The
existence of *y*-*y* (representing 10^{16} ) is not a problem here, because we can distinguish *yy* and *y*-*y* as long as we
always use separators.

Source: ACM-ICPC Japan Alumni Group Practice Contest
, for World Finals, Tokyo, Japan, 2008-02-24

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/