Jukebox

The ICPC judges are preparing a party for the opening ceremony. For the party, they want to add a playlist of several songs to the jukebox software (a simple MP3 player). However, there are so many songs on the computer that it is hard to find the ones they want, so they must use the search feature many times.

In this jukebox, when you search for a string $s$, the software returns every song whose title or artist name contains $s$ as a substring. A string $s$ is a substring of a string $t$ if $t$ contains all the characters of $s$ as a contiguous sequence (for example, 'bc' is a substring of 'abcd', but 'ac' is not). To save their precious time, whenever they look for a song they always use one of that song's golden strings, i.e. one of the shortest strings for which the search returns only the song they want.

In the example above, one possible golden string for the song 'johnnatan' is 'ta'. Note that 'ta' is not a substring of any other song's title or artist name. Note also that there is no string of length 1 that uniquely identifies the song 'johnnatan'.

They discovered that by removing the artist field from some of the songs they can obtain even shorter golden strings. For the song 'john' there is no golden string; however, if the artist field is removed from every other song, the string 'c' becomes the golden string for 'john'.

Given the song list (each song has a title and an artist), your task is to determine the minimum possible sum of the golden string lengths over all songs, when you are allowed to remove the artist field from some of the songs. Removing a song's artist field means that song no longer uses its artist name, neither for matching a search nor as a source of its own golden strings. The figure above shows one possible best result with the golden strings in bold; in this case the minimum sum of the golden string lengths is 10.

The input contains several test cases. The first line of each test case contains one integer $N$ ($1 \le N \le 30$), the number of songs. Then follow $2N$ lines, one pair per song: the first line of a pair is the song title and the second line is the artist name. Both titles and artist names are strings of lowercase letters and underscores ('_') only, with length between 1 and 30, inclusive. There are at most 6 distinct artists in the list.

The end of the input is indicated by $N = 0$.

For each test case, output a single line with the minimum sum of the golden string lengths. You may assume that a solution always exists.