주크박스

ICPC 심사위원단이 개막식 파티를 준비하고 있다. 파티를 위해, 간단한 MP3 재생기인 주크박스 소프트웨어에 여러 곡을 담은 재생 목록을 추가하려고 한다. 그런데 컴퓨터에 곡이 너무 많아서 원하는 곡을 찾기가 어렵고, 그래서 검색 기능을 여러 번 사용해야 한다.

이 주크박스에서 문자열 $s$ 를 검색하면, 소프트웨어는 제목 또는 아티스트 이름에 $s$ 를 부분 문자열로 포함하는 모든 곡을 반환한다. 문자열 $s$ 가 문자열 $t$ 의 부분 문자열이라는 것은, $t$ 안에 $s$ 의 모든 문자가 연속으로 나타난다는 뜻이다(예를 들어 'bc' 는 'abcd' 의 부분 문자열이지만, 'ac' 는 아니다). 소중한 시간을 아끼기 위해, 그들은 어떤 곡을 찾을 때 항상 그 곡의 골든 문자열(golden string) 중 하나를 사용한다. 골든 문자열이란, 검색 결과로 오직 그 곡 하나만 반환되게 하는 가장 짧은 문자열을 말한다.

위 예시에서 곡 'johnnatan' 의 골든 문자열 중 하나는 'ta' 이다. 'ta' 는 다른 어떤 곡의 제목이나 아티스트 이름에도 부분 문자열로 등장하지 않는다. 또한 곡 'johnnatan' 을 유일하게 식별하는 길이 1짜리 문자열은 존재하지 않는다.

한편, 일부 곡에서 아티스트 필드를 제거하면 더 짧은 골든 문자열을 얻을 수 있다는 것을 알게 되었다. 곡 'john' 에는 골든 문자열이 존재하지 않는다. 하지만 다른 모든 곡에서 아티스트 필드를 제거하면 문자열 'c' 가 곡 'john' 의 골든 문자열이 된다.

주어진 곡 목록(각 곡은 제목과 아티스트로 이루어진다)에 대해, 일부 곡의 아티스트 필드를 제거하는 것이 허용될 때 얻을 수 있는 모든 곡의 골든 문자열 길이 합의 최솟값을 구하라. 어떤 곡의 아티스트 필드를 제거하면, 그 곡은 검색 일치에서도, 그 곡 자신의 골든 문자열 후보에서도 아티스트 이름을 더 이상 사용하지 않는다. 위 그림은 골든 문자열을 굵게 표시한 가능한 최적의 결과이며, 이때 골든 문자열 길이 합의 최솟값은 10이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 곡의 수를 나타내는 정수 $N$ ($1 \le N \le 30$) 이 주어진다. 이어서 곡마다 한 쌍씩, 총 $2N$ 개의 줄이 주어진다. 각 쌍의 첫 줄에는 곡 제목이, 둘째 줄에는 아티스트 이름이 주어진다. 제목과 아티스트 이름은 모두 소문자 알파벳과 밑줄('_')로만 이루어지며, 길이는 1 이상 30 이하이다. 목록에는 서로 다른 아티스트가 최대 6명까지 등장한다.

입력의 끝은 $N = 0$ 으로 주어진다.

각 테스트 케이스마다 골든 문자열 길이 합의 최솟값을 한 줄에 출력한다. 항상 해가 존재한다고 가정해도 된다.