Background

Special for beginners, ^_^

Description

无向图中的汉密尔顿是指一条路径，它经过每个点有且仅有一次。每条汉密尔顿路径的 权值定义为这条路径中每条边的权值之和。这是最近 WZK 教小 Y 学的图论知识，现在 WZK 想检验一下小Y的举一反三的能力，提出了以下问题： 有一个n 个顶点的无向图（顶点从 0到 n-1 标号），它的每一个顶点都标有一个字符串 label[i] ，两两顶点间都存在一条边，一条从 i 到 j 的 边 的 权 值 定 义 为 length(label[i])^2+length(label[j])^2-length(LCP(label[i],label[j]))^2，LCP指的 是两个字符串的最长公共前缀。现在，要求一个从顶点 0出发，到顶点 1结束的权值最小的 汉密尔顿路径。

Format

Input

第一行，一个整数 n (2<=n<=50)。 接下来n行，每行一个不超过 50个字母的小写字符串 label[i],i从0到n-1。

Output

仅一行，为要求的汉密尔顿路径的权值。

Samples

4
abcd
aecgh
abef
aecd

91

Limitation

1s, 1024KiB for each test case.