Migrated from Lutece 445 Shortest String

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

NEW is depressed by his fault in the online-contest, so he is determing to read dozens of problems to hence his ability of setting a question (￣.￣)+ .

But, as you see, NEW's english is really poor, and reading a long passage is hard for him ╮（╯＿╰）╭ .

In order to achieve his goal, NEW dicided to make full use of his strange talent to read $n$ strings together （￣︶￣）↗ , which leads to the problem list below: Here comes $n$ strings $a_1, a_2,\cdots , a_n$, NEW wanna make a new string B which contains $a_1, a_2,\cdots$ and $a_n$ (It means that $a_1,a_2,\cdots ,a_n$ are all B's substring). Please help NEW to figure out the minimum length of $B$. （＞﹏＜）

Input

There are several test cases.

One interger $N$ ($0< N < 15$) is given in the first line

Then following $N$ lines, each line contains one string. (The whole length of $N$ string is less than $3\times 10^5$)

Output

One line for each case, the minimum length of $B$

Samples

3
abac
acd
cdb

6

Note

In the sample, $B$ is abacdb which have minimum length.

Resources

5th BUPT Programming Contest Final