The 4th(2009) ACM Programming Contest of HUST  Onsite Contest
From: 20091206 12:00:00
To: 20091206 17:00:00
Now: 20170920 01:09:55
Status: Public
J  Trie
Time Limit: 1s
Memory Limit: 128MB
Submissions: 112 Solved: 39
 Description
 In computer science, a trie, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Each position in the tree shows what key it is associated with and All the descendants of a node have a common prefix of the string associated with that node, have and only have one more character than its father node. the root of the trie is associated with the empty string.
For example, if we put 6 words of “to”, “tea”, “ted”, “ten”, “a”, “inn” to a trie, it will be the form of figure.
In the computer science, a trie is a tree. For a tree, we define the leave node is the node without any descendants and only have an edge connect in. So in this example, the leave node is “to”, “tea”, “ted”, “ten”, “a” and “inn”. And we define the distance between two node is the minimum edge from a node to another node must pass. So the distance between “a” and “te” is 3, “to” and “inn” is 5.
Finally, we define the value of a node is the sum of the node to the entire leave node’s distance. And the value of a tree is equal the value of a node which have the minimum value.
Now give you a list of words. Put them into a trie, and calculate the value of this trie.
 Input
 The first line is T, indicate there are T cases.
For each case, the first line is N, indicate there are N words.
Next N lines, each line have a word only include the lower case letters and no two words are the same. (N<=50 and the length of a word less than 10)
 Output
 For each case output a line with the value of the trie.
 Sample Input

2
6
a
to
tea
ted
ten
inn
4
sa
sb
sc
sd
 Sample Output

Case #1: 13
Case #2: 5
/////////////////////////////////////
For the second case, if the root has only one child, it’s a special leaf and must be calculate.
 Hint
 Source
 Hong Zehua, HUST Campus 2009