Many interactive computer programs use pick lists that allow users to select responses using as few keystrokes as possible. A pick list is just an alphabetized list of strings, but the user only has to type enough characters of a given string to identify it uniquely. For example, in the following pick list, a user could select REPORTS just by pressing R. To select ADDRESSES, a user would have to type ADDR.
ADDITIONAL INFORMATION ADDRESSES NAMES REPORTS SPREADSHEETS
The input for this problem consists of one or more pick lists. Each pick list consists of a line containing a nonnegative integer N, representing the number of strings in the list, followed by N lines containing the strings in alphabetical order (with respect to the ASCII collating sequence). A pick list with N=0 signals the end of the input. For each nonempty pick list, output a line containing the minimum number of keystrokes sufficient to uniquely identify any string in the list.
Input must be read from the file "prob37.in", and output must be
written to the file "prob37.out". All output to the screen will be
ignored.
<BOF> 1 albatrosses 2 Pigs on Mars! Pigs on the wing? How odd! 4 slink slipper slop sloppy 0 <EOF>
1 9 5