City Merger

Recent improvements in information and communication technology have made it possible to provide municipal services to a wider area more quickly and at lower cost. Encouraged by this, and to save their limited budgets, the mayors of many cities have begun discussing mergers of their cities.

Of course, there are many obstacles to actually carrying out a planned merger. Each city has its own culture that its citizens are proud of. One of the biggest sources of friction is the name of the new city. Every citizen insists that the name of the new city must contain the original name of their own city, at least as a part of it. Simply concatenating all of the original names, however, would make the name far too long for everyday use.

A group of mayors has asked you to write a program that finds the shortest possible name for the new city that includes all of the original names of the merged cities. If two or more names share a common part, that part may be overlapped. For example, if the cities "FUKUOKA", "OKAYAMA", and "YAMAGUCHI" are merged, then "FUKUOKAYAMAGUCHI" is a name that includes all three original names. Although this name contains all the letters of "FUKUYAMA" in order, they do not appear as a consecutive substring, so "FUKUYAMA" is not considered to be included.

An original name is considered included only if it appears as a consecutive substring.

The input is a sequence of datasets. Each dataset begins with a line containing a positive integer $n$ ($n \le 14$), the number of cities to be merged. The next $n$ lines each contain the name of one city, written in uppercase letters. No original city name is longer than 20 characters, and no two cities have the same name.

The end of the input is indicated by a line containing a single $0$.

For each dataset, print the length of the shortest possible name for the new city on its own line. Do not print any other characters.