近年来，信息与通信技术的进步使得以更低的成本、更快速地向更广泛的地区提供市政服务成为可能。受此启发，也可能是为了节省本就不充裕的资金，许多城市的市长开始讨论合并他们所在的城市。

当然，要将计划中的合并付诸实践，还面临着许多障碍。每个城市都有自己独特的文化，市民们为此感到自豪。其中最大的摩擦来源之一就是新城市的命名。所有市民都会坚持要求新城市的名字中必须至少包含他们原本城市的名字作为其一部分。然而，简单地将所有原名拼接在一起，会使名字过长，不便于日常使用。

一组市长请求你编写一个程序，寻找一个尽可能短的新城市名称，使其包含所有待合并城市的原始名称。如果两个或多个城市的名字有重合的部分，它们可以相互重叠。例如，如果要合并 “FUKUOKA”、“OKAYAMA” 和 “YAMAGUCHI” 这三个城市，“FUKUOKAYAMAGUCHI” 就是一个包含了所有这三个原始城市名称的名字。虽然这个名字按顺序包含了城市名称 “FUKUYAMA” 的所有字符，但它们并没有作为连续的子串出现，因此不认为 “FUKUYAMA” 被包含在该名字中。

输入格式

输入由多个数据集组成。每个数据集以包含一个正整数 $n$ ($n \le 14$) 的行开始，表示要合并的城市数量。接下来的 $n$ 行包含这些城市的名字，每个名字由大写英文字母组成，每行一个。你可以认为每个原始城市名字的长度不超过 20 个字符。当然，没有两个城市具有相同的名字。

输入结束由仅包含一个零的行表示。

输出格式

对于每个数据集，在一行中输出新城市可能的最短名称的长度。输出中不应包含任何其他字符。

样例

输入样例 1

3
FUKUOKA
OKAYAMA
YAMAGUCHI
3
FUKUOKA
FUKUYAMA
OKAYAMA
2
ABCDE
EDCBA
4
GA
DEFG
CDDE
ABCD
2
ABCDE
C
14
AAAAA
BBBBB
CCCCC
DDDDD
EEEEE
FFFFF
GGGGG
HHHHH
IIIII
JJJJJ
KKKKK
LLLLL
MMMMM
NNNNN
0

输出样例 1

16
19
9
9
5
70